forked from menault/TD4_DEV51_Qualite_Algo
117 lines
3.7 KiB
Markdown
117 lines
3.7 KiB
Markdown
# TD4 - DEV5.1 Qualité algorithmique
|
|
## Exo 2
|
|
### function_1()
|
|
pire des cas de parcours nombre1\*nombre2, donc complexité = O(nombre1\*nombre2)
|
|
|
|
### function_2()
|
|
Boucle parcourue jusqua que x = 0 donc il ya a x parcours de la boucle, complexité = O(x)
|
|
|
|
### function_3()
|
|
un seul parcour de la boucle, complexité = O(1)
|
|
|
|
## Exo 3
|
|
### sort_students()
|
|
```
|
|
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);
|
|
}
|
|
}
|
|
```
|
|
Si l'on suppose que:
|
|
- La complexité de “malloc” est O(1)
|
|
- La complexité de “free” est O(1)
|
|
|
|
On commence par calculer les complexité algorythmique des fonctions comprises dans sort_students().
|
|
|
|
**D'abord la complexité de bublesort() :**
|
|
```
|
|
void bubblesort(int* array, int length)
|
|
{
|
|
int swapped, i, tmp;
|
|
do
|
|
{
|
|
swapped = 0;
|
|
for(i=1;i<length;i++)
|
|
{
|
|
if(array[i-1] > array[i])
|
|
{
|
|
tmp = array[i-1];
|
|
array[i-1] = array[i];
|
|
array[i] = tmp;
|
|
swapped++;
|
|
}
|
|
}
|
|
} while(swapped==1);
|
|
}
|
|
```
|
|
La boucle while continue tant que swapped = 1, or celle si ne l'est que lorsqu'il a parcourue entierement la boucle sans l'avoir modifier.
|
|
Dans le meilleur des cas c'est 1 seul parcours, dans le pire c'est n² car il doit reinverser tout le tableau.
|
|
Donc O = n².
|
|
|
|
|
|
**Ainsi que de find_rank_student():**
|
|
```
|
|
int <find_rank_student>(int student_grade, int* grades_array, int students_number)
|
|
{
|
|
int position = -1;
|
|
int i = 0;
|
|
bubblesort(grades_array,students_number);
|
|
for(i = students_number-1; i >= 0; i--)
|
|
{
|
|
if(grades_array[i] == student_grade)
|
|
{
|
|
position = students_number-i;
|
|
break;
|
|
}
|
|
}
|
|
return position;
|
|
}
|
|
```
|
|
Cette fonction contient bubblesort() qui a une complexité de N². De plus elle contien une boucle for qui s'execute students_number-1 fois.
|
|
Dans le pire des cas cette fonction la boucle fera donc n-1 parcours. La complexité algorythmique est donc de O(n²+(n-1)).
|
|
|
|
|
|
On peut donc enfin calculer la complexité de sort_students():
|
|
```
|
|
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);
|
|
}
|
|
}
|
|
```
|
|
|
|
Il y a trois boucle dans sort_students, l'une avec un malloc de complexité O(1) qui s'éxecute grades_number fois, un bublesort qui depend de students_number et deux autre boucles qui séxecute students_number fois. La premiere boucle sexecute donc n fois, le bublesort a une complexité de N², la seconde boubcle contient find_rank_student(), elle a donc une complexité de N*(N²+(N-1)) et enfin il y a un free qui vaut donc 1.
|
|
Si l'on calcule cela fait donc = M(1+N+N²+N*(N²+(N-1))+1)
|
|
= M(2+N+N²+N3+N²-N)
|
|
= M(N3+2N²+2)
|
|
On garde la plus complexité la plus elevé donc O(M*N3)
|
|
|
|
### Exo 4
|
|
Mon code se compose en fait de 2 buble sort, la complexité de sort_bubble_array() donc de O(n²), et celle de bublesort_multi_array() est de O(n²+n²) donc O(n²) |