forked from menault/TD4_DEV51_Qualite_Algo
52 lines
2.3 KiB
Markdown
52 lines
2.3 KiB
Markdown
|
# Ex2 - Calculs de complexité de fonctions
|
||
|
|
|
||
|
|
Complexité algorithmique :
|
||
|
|
- fonction_1 : O(n*m)<br>
|
||
|
|
Cette fonction contient des boucles imbriquées. Dans le pire des cas, il faudra parcourir n x m.
|
||
|
|
- fonction_2 : O(n) <br>
|
||
|
|
La boucle while s'exécute au maximum n fois.
|
||
|
|
- fonction_3 : O(1)<br>
|
||
|
|
Cette fonction ne contient pas de boucle. Chaque condition est évaluée une seule fois, indépendamment de la taille des données d'entrée.
|
||
|
|
|
||
|
|
# Ex3 - student_rank.c
|
||
|
|
|
||
|
|
|
||
|
|
```
|
||
|
|
void sort_students(int** students_rank, int** students_array, int students_number, int grades_number)
|
||
|
|
{
|
||
|
|
int i = 0, j = 0;
|
||
|
|
for(i = 0; i < grades_number; i++)
|
||
|
|
{
|
||
|
|
int * grades = (int*) malloc(students_number*sizeof(int));
|
||
|
|
for(j = 0; j < students_number; j++)
|
||
|
|
{
|
||
|
|
grades[j] = students_array[j][i];
|
||
|
|
}
|
||
|
|
bubblesort(grades,students_number);
|
||
|
|
for(j = 0; j < students_number; j++)
|
||
|
|
{
|
||
|
|
students_rank[j][i] = find_rank_student(students_array[j][i],grades,students_number);
|
||
|
|
}
|
||
|
|
free(grades);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
1. La boucle externe s'exécute m fois, où m représente grades_number La complexité est donc O(m).
|
||
|
|
2. La copie des notes prend O(n),où n est le nombre d'étudiants.
|
||
|
|
3. Le tri bublesort a une complexité de O(n²)
|
||
|
|
4. find_rank_student la complexité de cette étape est dominée par le tri des étudiants bubblesort donc O(n²).
|
||
|
|
|
||
|
|
À chaque itération (pour chaque groupe de notes m), les opérations dominantes sont le tri des n étudiants avec une complexité de O(n²) ainsi la complexité totale est O(m*n²).
|
||
|
|
|
||
|
|
## Ex4 - Algorithme de tri
|
||
|
|
|
||
|
|
### 1. Tri des sous-listes :
|
||
|
|
Si une sous-liste a une taille de m, la complexité du tri de cette sous-liste est O(m²) car l'algorithme de tri parcourt la sous-liste m et, à chaque fois, il effectue m-1 comparaisons.
|
||
|
|
il y a n sous-listes au total. Donc, la complexité totale du tri des sous-listes est O(n*m²).
|
||
|
|
|
||
|
|
### 2. Tri liste principale
|
||
|
|
À chaque itération, nous comparons les sommes des sous-listes. Calculer la somme des éléments d'une sous-liste prend O(m) temps (car la somme des m éléments de la sous-liste doit être calculée).
|
||
|
|
Donc, pour chaque comparaison, la complexité est O(m) (pour calculer la somme), et il y a O(n²) comparaisons au total dans le tri à bulle de la liste principale. La complexité du tri de la liste principale est donc O(n²*m)
|
||
|
|
|
||
|
|
Donc, la complexité totale est O( n*m² + n²\*m )
|