Rapport TD4 :

Exercice 2 :

Fonction n°1 : complexité algorithmique O(n*m)
(avec n = len(tab1) et m = len(tab2) ). Car l'on parcours deux tableau et que l'on compare ces derniers
Fonction n°2 : complexité algorithmique O(n)
Car ici on boucle tant que x > 0 et l'on retire 1 à chaque itérantion , donc la boucle est effectué x fois
Fonction n°3 : complexité algorithmique de O(1)
Car la fonction vas prendre la valeur de x et effectuer une seule opération en fontion de cette dernière.

Dans un premier temps, décomposon le code.

on retrouve au tout début du code une boucle :
```
for(i = 0; i < grades_number; i++){
int *grades = (int*) malloc(students_number * sizeof(int));
```
la complexité est donc de O(n)
(Ou n = grades_number)
dans un second temps, on peut retrouver cette partie de code :
```
for (j = 0; j < students_number; j++)
{
    grades[j] = students_array[j][i];
}
```
Ici la complexité est de O(m) car on boucle sn fois.
(Ou m = student_number)
troisième portion de code :
```
bubblesort(grades, students_number);
```
Comme bubblesort parcours le tableau pour le trier chaque élément doit être comparé au autre. La complexité est donc de O(m^2)
Quatrième partie de code :
```
for (j = 0; j < students_number; j++)
{
    students_rank[j][i] = find_rank_student(students_array[j][i], grades, students_number);
}
```
Ici il nous faut la complexité algorythmique de find_rank_student, cette dernière est de O(m^2), donc la complexité de cette boucle est de O(m)*O(m^2)=O(m^3)
Dernière partie de code :
```
free(grades);
```
Ici la complexité algorithmique est de O(1)

Donc la complexité algorithmique de cette fonction est de : O(n)*(O(m)+O(m²)+O(m^3)+O(1))

On obtient donc la complexité suivante : O(n*m^3)

(voir Ex4_sort.py)

Complexité algorithmique :

Complexité de bubblesort_array : O(n^2) car chaque élément à des chance d'être déplacé plusieurs fois.
Complexité de bubblesort_multi_array :
- première partie de code :
```
for subarray in array:
    bubblesort_array(subarray)
```
  ici la complexité algorithmique est de O(n*m^2) (où n = longueur du tableau pricipal et m = taille des sous taableaux)
- seconde partie de code :
```
while (swap > 0):
    swap = 0
    for i in range(1, len(array)):
        if sum(array[i-1]) > sum(array[i]):
            temp = array[i-1]
            array[i-1] = array[i]
            array[i] = temp
            swap += 1
```
  ici la complexité algorithmique est de O(n^2*m)
- calcul final : la complexité algorithmique est donc de O(n^2 * m + n * m2). cenpendant la complexité dépend donc des tailles du tableau et sous-tableau. Nous avons donc trois possibilité :
  - première possibilité : n > m Alors (n^2 * m) > (n * m^2), donc la complexité algorithmique est de O(n^2 * m)
  - seconde possibilité : m > n Donc (n * m^2) > (n^2 * m), donc la complexité algorithmique est de O(n*m^2)
  - dernière possibilité : n = m Ici si n = m alors la complexité algorithmique est bien de O(n^2 * m + n * m^2)