forked from menault/TD4_DEV51_Qualite_Algo
87 lines
2.3 KiB
Markdown
87 lines
2.3 KiB
Markdown
# TD4_DEV51_Qualite_Algo
|
|
###### par SCHIED Killian
|
|
|
|
## Exercice 2
|
|
|
|
### Fonction 1
|
|
|
|
La complexité algorithmique de la fonction 1 est de O(n*m) dans le pire des cas (si on explore l'intégralité des 2 tableaux) ou de O(n+m) dans le meilleur des cas (si les 2 tableaux contiennent une liste qu'avec la même valeur (par exemple un tableau qui contient que des 1)).
|
|
|
|
### Fonction 2
|
|
|
|
La complexité algorithmique de la fonction 2 est de O(x) dans le pire des cas (si le nombre est positif, il va le décrémenter de 1 jusqu'à qu'il soit égal à 0) ou de O(1) dans le meilleur des cas (si le nombre et négatif, il va retourner directement la valeur).
|
|
|
|
### Fonction 3
|
|
|
|
La complexité algorithmique de la fonction 3 est de O(1) car il change valeur si x est supérieur, égal ou inférieur à 0 puis il retourne la valeur.
|
|
|
|
## Exercice 3
|
|
|
|
La complexité algorithmique de la fonction "sort_students" est de : O(n*(m^3)).
|
|
|
|
```
|
|
// O(n*(m^3)) (on garde seulement m^3 et les autres s'annulent)
|
|
void sort_students(int** students_rank, int** students_array, int students_number, int grades_number)
|
|
{
|
|
int i = 0, j = 0;
|
|
// O(n)
|
|
for(i = 0; i < grades_number; i++)
|
|
{
|
|
int * grades = (int*) malloc(students_number*sizeof(int)); // O(1)
|
|
// O(m)
|
|
for(j = 0; j < students_number; j++)
|
|
{
|
|
grades[j] = students_array[j][i];
|
|
}
|
|
bubblesort(grades,students_number); // O(m^2)
|
|
// O(m*m^2) <=> O(m^3)
|
|
for(j = 0; j < students_number; j++)
|
|
{
|
|
students_rank[j][i] = find_rank_student(students_array[j][i],grades,students_number); // O(m^2)
|
|
}
|
|
free(grades); // O(1)
|
|
}
|
|
}
|
|
|
|
// O(n^2)
|
|
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);
|
|
}
|
|
|
|
// O(n^2) (car O(n) s'annule)
|
|
int find_rank_student(int student_grade, int* grades_array, int students_number)
|
|
{
|
|
int position = -1;
|
|
int i = 0;
|
|
bubblesort(grades_array,students_number); // O(n^2)
|
|
// O(n)
|
|
for(i = students_number-1; i >= 0; i--)
|
|
{
|
|
if(grades_array[i] == student_grade)
|
|
{
|
|
position = students_number-i;
|
|
break;
|
|
}
|
|
}
|
|
return position;
|
|
}
|
|
```
|
|
|
|
## Exercice 4
|
|
|
|
La complexité algorithmique de l'algorithme dans [sort_algorithm.py](./sort_algorithm.py) est de O(n^2 + 2*m). |