# Rapport TD4 :

## Exercice 2 : 
1) Fonction n°1 : complexité algorithmique  O(n*m) <br>
    (avec n = len(tab1) et m = len(tab2) ). Car l'on parcours deux tableau et que l'on compare ces derniers

2) Fonction n°2 : complexité algorithmique O(n) 
<br>
    Car ici on boucle tant que x > 0 et l'on retire 1 à chaque itérantion , donc la boucle est effectué x fois

3) Fonction n°3 : complexité algorithmique de O(1)
<br>
    Car la fonction vas prendre la valeur de x et effectuer une seule opération en fontion de cette dernière.

## Exercice 3 :

Dans un premier temps, décomposon le code.<br>
- 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)<br>
    (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.<br>
    (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)) <br>

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


## Exercice 4 :
(voir *Ex4_sort.py*)<br>


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)