forked from menault/TD4_DEV51_Qualite_Algo
23 lines
767 B
Markdown
23 lines
767 B
Markdown
|
Hugo Raban et Patrick Felix-Vimalaratnam
|
|||
|
|
|
|||
|
|
# Ex 2
|
|||
|
|
|
|||
|
|
## Code 1
|
|||
|
|
|
|||
|
|
La complexité de ce code est de O(n*m) car pour chaque valeur du tableau1 on va regarder toutes les valeurs du tableau2.
|
|||
|
|
|
|||
|
|
## Code 2
|
|||
|
|
|
|||
|
|
La complexité de ce code est de O(n) car le nombre d'itération de la boucle dépend de la valeur de x.
|
|||
|
|
|
|||
|
|
## Code 3
|
|||
|
|
|
|||
|
|
La complexité de ce code est de O(1) car peu importe la valeur de x, il n'y a pas de boucle.
|
|||
|
|
|
|||
|
|
# Ex 3
|
|||
|
|
|
|||
|
|
Le code trie récursivement chaque sous-tableau, puis trie le tableau courant selon la somme des sous-tableaux.
|
|||
|
|
|
|||
|
|
À chaque niveau, le tri coûte O(M*log(M)) et chaque comparaison parcourt tous les éléments du sous-tableau (O(M^(n−1))).
|
|||
|
|
|
|||
|
|
Donc pour un tableau à N dimensions et M éléments par niveau, la complexité totale est O(M^N*log(M)).
|