4.3 KiB
Exercice 2)
Fonction 1 :
Dans cette fonction nous avons deux tableaux, un tableau 1 de longueur net un tableau 2 de longueur m. Nous allons itérer sur tous les éléments du tableau 1, donc la complexité de cette boucle est de O(n). Ensuite, nous allons itérer sur tous les éléments du tableau 2 et vérifier si l'élément du tableau 1 est égal à l'élément du tableau 2, donc dans le meilleur des cas, la complexité de cette boucle est de O(n), mais dans le pire des cas, la complexité est de O(n*m). Donc la complexité globale de cette fonction est de O(n*m).
Fonction 2 :
La complexité est de O(x) car on fait une boucle qui va itérer x fois, jusqu'à ce que x soit égale à 0. Dans cette boucle nous allons réaliser deux opérations avec une complexité de O(1), ce qui ne change pas la complexité globale qui restera à O(x).
Fonction 3 :
On retrouve trois blocs conditionnels qui ont chacun un coup de O(1) et une seule condition peut être vraie. Donc la complexité globale de cette fonction est de O(1)
Exercice 3)
Fonction sort_students :
Dans la fonction sort_students nous retrouvons une première boucle qui va itérer sur grades_number qu'on va noté n et qui englobe toute la fonction.
Dans cette boucle nous allons faire une allocation mémoire avec malloc qui a une complexité de O(1), ce qui veut dire que la complexité de cette boucle est de O(n * 1) = O(n).
Ensuite, nous avons une deuxième boucle qui va itérer sur students_number qu'on va noté m. Dans cette boucle nous copions les notes des étudiants pour les mettre dans le tableau grades. Nous effectuons cette opération n fois, donc la complexité globale de la fonction est de O(n * m).
Après nous appelons la fonction bubble_sort avec le tableau grades et students_number comme arguments. bubble_sort qui est une fonction de tri, où dans le pire des cas, la complexité est de O(m^2). Donc la complexité globale de la fonction sort_students est de O(n * m + m^2) = O(n * m^2).
Nous retrouvons une dernière boucle qui va itérer sur students_number, donc la complexité de cette boucle est de O(m). Dans cette boucle nous allons appeler la fonction find_rank_student.
Fonction find_rank_student :
Cette fonction appelle la fonction bubble_sort avec le tableau grades_array et students_number comme arguments. bubble_sort qui est une fonction de tri, où dans le pire des cas, la complexité est de O(m^2). Ensuite, nous avons une boucle qui va itérer sur students_number, donc la complexité de cette boucle est de O(m). Donc la complexité globale de la fonction find_rank_student est de O(m^2 + m) = O(m^2).
Fonction sort_students :
La complexité de la fonction find_rank_student est de O(m^2), et nous l'appelons m fois, donc la complexité globale de la fonction sort_students est de O(n * m^2 + m * m^2) = O(n * m^2 + m^3) = O(n*m^3).
Exercice 4)
Code python : sortarray.py
Tri interne :
Pour chaque sous-liste de M valeurs dans le tableau, nous utilisons le tri par sélection :
Le tri par sélection parcourt la liste pour trouver le minimum et l'échange avec le premier élément. Ensuite, il répète cela pour les éléments restants.
Si nous avons N sous-listes de M valeurs, la complexité de l'algorithme est de O(N*M^2).
Tri externe :
Pour trier les N sous-listes en fonction de leurs sommes, nous utilisons un algorithme similaire au tri par sélection sur les sous-listes. Nous avons donc une complexité de O(N^2).
Calcul des sommes :
Avant de comparer les sous-listes dans le tri externe, il faut calculer la somme de chaque sous-liste. Chaque somme nécessite M opérations, et il y a N sous-listes. Donc, le coût total pour calculer les sommes est de O(N*M).
Complexité totale :
La complexité totale dépend de la relation entre N et M. Si N est beaucoup plus grand que M, la complexité de l'algorithme est dominée par le tri externe, donc la complexité totale est de O(N^2). Si M est beaucoup plus grand que N, la complexité de l'algorithme est dominée par le tri interne, donc la complexité totale est de O(N*M^2). Si N et M sont de même ordre de grandeur, la complexité totale est de O(N*M^2 + N^2 + N*M).