TD4 - DEV5.1 Qualité algorithmique

EX 2 - Calculs de complexité des fonctions

function_1 : la complexité est O(n1 x n2) car il y a 2 tableaux qu'on doit dans le pire des cas traversés entièrement.

function_2 : La complexité est O(n) car on la boucle s'exécute x fois.

function_3 : La complexité est O(1) car il n'y aucune boucle.

EX 3 - student_rank.c

On a une boucle extérieure qui s'exécute g fois donc O(g).

On a l'allocation de la mémoire avec malloc qui est constante donc on a O(1).

Ensuite, on a une première boucle intérieure qui places des notes dans le tableau grades. La boucle s'exécute s fois donc on a O(s).

Maintenant, on a l'exécution de la fonction bubblesort. Cette fonction est un trie à bulle du tableau grades.
Sa complexité est O(s^2) car elle compare chaque paire d'éléments s fois.

On a une deuxième boucle intérieure qui, elle, détermine le rang de chque student en appelant la fonction find_rank_student.
On passe à l'analyse de find_rank_student pour connaitre sa complexité. Elle trie à nouveau le tableau grades_array avec bubblesort donc on a une complexité O(s^2).
Ensuite, elle recherche la position de la note de l'étudiant avec une boucle simple ce qui nous donne O(s). Donc la complexité totale de find_rank_student est O(s^2) car la recherche est anecdotique car sa grandeur est inférieur à celle du trie.

On retourne dans la deuxième boucle inférieure, la fonction find_rank_student est appelée s fois donc à chque appel, sa complexité est O(s^2). La complexité totale de la boucle est O(s x s^2) soit O(s^3).

Enfin, la complexité totale de sort_students est O(g x s^3). On atteint cette complexité car la boucle extérieure s'exécute g fois et à chaque itération, on a :
- une boucle de complexité O(s).
- un tri O(s^2).
- une boucle avec appels O(s^3).

On a donc O(g x (s + s^2 + s^3)). Or on a vu précédemment que l'on peut simplifier par le terme de plus haute grandeur soit O(s^3).

On obtient : O(g x s^3).

EX 4 - Algorithme de tri

L'algorithme se trouve dans le fichier python.

Tri des sous-tableaux (Étape 1) :

La complexité algorithmique de l'algorithme est composée des étapes suivantes :

1. Tri des sous-tableaux : Chaque sous-tableau de taille M est trié en O(M log M), et il y a N sous-tableaux. La complexité de cette étape est donc O(N * M log M).
2. Calcul des sommes des sous-tableaux : Pour chaque sous-tableau, la somme est calculée en O(M), ce qui donne une complexité totale de O(N * M).
3. Tri des sous-tableaux par leur somme : Le tri des N sous-tableaux en fonction de leurs sommes est effectué en O(N log N).
4. Extraction des résultats : Cette étape a une complexité de O(N).

La complexité globale de l'algorithme est donc :
O(N * M log M + N log N).