TD4_DEV51_Qualite_Algo/README.md

# RAPPORT

## EXO2

- **function_1(tableau1, tableau2)** :  
  - **Complexité algorithmique** : O(n * m)  
    - Dans le pire cas, où `n` est la taille du tableau 1 et `m` la taille du tableau 2.

- **function_2(x)** :  
  - **Complexité algorithmique** : O(x)  
    - La boucle `while` fait `x` itérations, et `x` est décrémentée de 1 jusqu'à 0.

- **function_3(x)** :  
  - **Complexité algorithmique** : O(1)  
    - En fonction de la valeur de `x`, une des trois conditions exécute une opération simple.

---

## EXO3

Pour cette fonction, on a :

- **La première boucle for** : O(g)
- **Malloc** : O(1)
- **Deuxième boucle for** : O(g * n)
- **Bubblesort** : O(g * n²)
- **Free** : O(1)
- **find_rank_student** : O(g * n²) pour Bubblesort + O(g * n) : O(g * n^3)

**Simplification :**
- On peut enlever les O(1) et conserver la complexité la plus élevée, donc O(g * n^3).

**Complexité algorithmique pour sort_student :** O(g * n^3)

---

## EXO4

Voici le code :

```python
def tri(t):
    for tab in t:
        for i in range(len(tab)):
            for j in range(len(tab) - 1):
                if tab[j] > tab[j + 1]:
                    tab[j], tab[j + 1] = tab[j + 1], tab[j]
    
    for i in range(len(t)):
        for j in range(len(t) - 1):
            if t[j][0] > t[j + 1][0]:
                t[j], t[j + 1] = t[j + 1], t[j]
    
    print(t)

tri([[3, 9, 6], [9, 3, 8], [10, 67, 55]])
```

Complexité algorithmique de ma fonction tri() :

   - Pour m éléments, la complexité algorithmique de chaque sous-liste est O(m²), multipliée par le nombre de sous-listes, cela fait : O(n * m²).
   - Pour le tri final, la complexité algorithmique est O(n²).

On garde la plus élevée, donc pour ma fonction : O(n * m²) + O(n²).