TD4: Complexité algorithmique

Exercice 2

function_1(tableau1,tableau2)

La complexité de cette fonction est de O(n*m) avec n la taille du premier tableau et m la taille du second puisque le second tableau est parcouru n fois.

function_2(x)

La complexité de cette fonction est de O(n) car x réduit de 1 à chaque itération jusqu'à atteindre 0.

function_3(x)

La complexité de cette fonction est de O(1) car il n'y a pas de boucle ni d'appel à d'autres fonctions.

Exercice 3

On a une boucle qui englobe toute la fonction
A l'interieur de cette boucle on a :

• une boucle de complexité O(n)
• un bubblesort de complexité O(n²)
• une boucle contenant find_rank_student

find_rank_student possède à la fois une boucle et un bubblesort, on a donc une complexité de O(n+n²) qu'on peut simplifier en O(n²)
On a donc une complexité de O(m * n + n² + n²) que l'on peut simplifier en O(m * n²)

Exercice 4

Mon algorithme de tri est composé de deux bubblesort avec une complexité de O(N²) chacun
Pour le premier bubblesort, il y a la fonction sum() utilisée, possédant une complexité de O(M)
L'algorithme est donc de complexité O(M*N²)