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 :

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²).