1.8 KiB
TD 4 Berger Lucas
Exercice 2 :
Programme 1 :
Dans le pire des cas l'algorithme 1 aura une complexité algorithmique de O(n.m) avec n et m respectivement pour le tableau 1 et le tableau 2.
Dans le meilleur des cas l'algorithme 1 aura une complexité algorithmique de O(n) avec n pour le tableau 1.
Programme 2 :
La complexité algorithmique de la fonction 2 est O(n), où n est la valeur initiale de x.
Programme 3 :
La complexité de la fonction 3 est O(1) car elle effectue un nombre constant d'opérations, et ce indépendamment de la valeur de x.
Exercice 3 :
La complexité totale de sort_students est donnée par l'appel à bubblesort et à la fonction find_rank_student, qui ont toutes deux une complexité égale au nombre d'étudiants au carré (donc O(student_number²)), et ce, pour chaque itération de la boucle extérieure (grade_number est également une valeur décisive).
La complexité est donc égale à O(grade_number*student_number²) ou O(n*m²).
Exercice 4 :
VOIR algo.py CI-JOINT EXPLICATIONS CI-DESSOUS
Fonctionnement du programme :
Calcul des sommes des lignes :
Pour chaque ligne, nous calculons la somme de ses éléments, ce qui prend O(m) pour chaque ligne.
Donc, pour n lignes, la complexité de cette étape est O(n * m).
Tri par sélection :
L'algorithme de tri par sélection nécessite de comparer chaque élément avec tous les éléments suivants, ce qui donne une complexité de O(n²) pour trier n éléments.
Conclusion sur la complexité :
La complexité totale est la somme des étapes :
- Calcul des sommes :
O(n * m) - Tri par sélection :
O(n²)
La complexité totale est donc :
O(n * m + n²)
Donc, la complexité dépend à la fois du nombre de lignes n, du nombre d'éléments par ligne m, et du tri effectué dessus.