55 lines
1.8 KiB
Markdown
55 lines
1.8 KiB
Markdown
# 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.
|
|
|