forked from menault/TD4_DEV51_Qualite_Algo
53 lines
2.7 KiB
Plaintext
53 lines
2.7 KiB
Plaintext
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).
|
|
|