TD4_DEV51_Qualite_Algo/Readme.md

Exercice 1

1. function_1(tableau1, tableau2) :
   Dans cette fonction, il y a deux boucles imbriquées : la première parcourt tous les éléments de tableau1 (de taille n), et pour chaque élément, la deuxième boucle parcourt tableau2 (de taille m).
   Dans le pire des cas, si aucun élément ne correspond (ou si le break n'est jamais atteint), chaque élément de tableau1 sera comparé à tous les éléments de tableau2.
   Donc, la complexité de cette fonction est O(n \cdot m).

2. function_2(x) :
   Ici, on a une boucle while qui s’exécute x fois. À chaque itération, on effectue une addition et une décrémentation, qui prennent toutes les deux un temps constant.
   Du coup, la complexité est proportionnelle à x, donc O(x).

3. function_3(x) :
   Cette fonction contient uniquement des blocs if indépendants, qui s’exécutent chacun au maximum une seule fois. Il n’y a pas de boucle, donc chaque opération est constante.
   La complexité est donc O(1), car c’est constant peu importe la valeur de x.

---

Exercice 2

Pour analyser la complexité de la fonction sort_students, on décompose chaque étape :

1. Boucle externe sur les grades :
   La boucle externe parcourt tous les grades des étudiants, soit \text{grades\_number} itérations.

2. Allocation dynamique des notes :
   L’allocation du tableau grades est faite avec malloc, qui est supposée avoir une complexité O(1). Cela n’affecte donc pas significativement la complexité globale.

3. Copie des notes des étudiants :
   Dans la boucle interne :

   for(j = 0; j < students_number; j++) {
       grades[j] = students_array[j][i];
   }
   

   on copie les notes des \text{students\_number} étudiants, ce qui prend O(\text{students\_number}) par itération de la boucle externe.

4. Tri des notes avec bubblesort :
   La fonction bubblesort trie un tableau de taille \text{students\_number}, avec une complexité O(\text{students\_number}^2).

5. Trouver le rang de chaque étudiant :
   Ensuite, dans cette boucle interne :

   for(j = 0; j < students_number; j++) {
       students_rank[j][i] = find_rank_student(students_array[j][i], grades, students_number);
   }
   

   on appelle find_rank_student pour chaque étudiant. Cette fonction effectue :

   • Un tri par bulles O(\text{students\_number}^2),
   • Une recherche pour trouver le rang, qui prend O(\text{students\_number}).

   Donc, chaque appel à find_rank_student a une complexité totale de O(\text{students\_number}^2), et cette fonction est appelée \text{students\_number} fois par itération de la boucle externe. Cela donne une complexité O(\text{students\_number}^3) par itération de la boucle externe.

6. Libération de mémoire :
   Enfin, la mémoire allouée pour grades est libérée avec free, ce qui est une opération O(1).

Complexité totale :

La boucle externe s’exécute \text{grades\_number} fois, et la partie la plus coûteuse de la boucle interne est O(\text{students\_number}^3). La complexité globale de la fonction est donc :

O(\text{grades\_number} \cdot \text{students\_number}^3)

Conclusion :

La fonction sort_students a une complexité algorithmique de

O(\text{grades\_number} \cdot \text{students\_number}^3)

---

Exercice 3

Algorithme proposé

1. Tri des sous-dimensions :

   • Si on est sur un tableau 1D (le plus bas niveau), on le trie avec un tri par insertion.

2. Calcul des sommes des sous-dimensions :

   • Pour chaque sous-tableau, on calcule la somme des valeurs pour s’en servir comme critère de tri.

3. Tri des sous-dimensions par leurs sommes :

   • On trie les sous-dimensions avec un tri par insertion basé sur les sommes calculées.

4. Répétition pour les autres dimensions :

   • On applique ces étapes de façon récursive à chaque niveau du tableau.

Implémentation

Voici l'algorithme en Python :

# Fonction pour trier un tableau 1D avec un tri par insertion
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Déplacement des éléments plus grands que key
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Fonction pour trier un tableau multidimensionnel récursivement
def recursive_sort(T):
    # Si c'est un tableau 1D, on le trie
    if not isinstance(T[0], list):
        insertion_sort(T)
        return T
    
    # Trier chaque sous-dimension
    for i in range(len(T)):
        T[i] = recursive_sort(T[i])
    
    # Calculer les sommes des sous-dimensions
    sums = [sum(sum(val) if isinstance(val, list) else val for val in sublist) for sublist in T]
    
    # Trier les sous-dimensions en fonction de leurs sommes
    for i in range(1, len(T)):
        key_sum = sums[i]
        key_sublist = T[i]
        j = i - 1
        while j >= 0 and sums[j] > key_sum:
            sums[j + 1] = sums[j]
            T[j + 1] = T[j]
            j -= 1
        sums[j + 1] = key_sum
        T[j + 1] = key_sublist

    return T

# Exemple avec un tableau 2D
tableau = [[0, 3, 2], [9, 4, 5], [4, 1, 3]]
resultat = recursive_sort(tableau)
print(resultat)  # Résultat attendu : [[0, 2, 3], [1, 3, 4], [4, 5, 9]]

Exemple d’exécution

Prenons le tableau suivant :

 [ [0, 3, 2], [9, 4, 5], [4, 1, 3] ] 

1. Trier chaque ligne :

   • Première ligne : [0, 3, 2] \rightarrow [0, 2, 3]
   • Deuxième ligne : [9, 4, 5] \rightarrow [4, 5, 9]
   • Troisième ligne : [4, 1, 3] \rightarrow [1, 3, 4]

   
   [ [0, 2, 3], [4, 5, 9], [1, 3, 4] ]
   

2. Calculer les sommes :

   • [0, 2, 3] \rightarrow 5
   • [4, 5, 9] \rightarrow 18
   • [1, 3, 4] \rightarrow 8

3. Trier les lignes en fonction des sommes :

   
   [ [0, 2, 3], [1, 3, 4], [4, 5, 9] ]
   

Complexité

Analyse :

1. Tri des tableaux 1D :

   • Pour M éléments, le tri par insertion a une complexité de O(M^2).

2. Tri des sous-tableaux (dimensions N > 1) :

   • Chaque sous-tableau contient M^{N-1} éléments. Trier ces sous-tableaux coûte O(M^{N-1} \cdot M^{N-1}) = O(M^{2(N-1)}).

3. Calcul des sommes :

   • Calculer les sommes pour M^{N-1} sous-tableaux coûte O(M^N).

4. Complexité totale :

   • L'algorithme s’applique de façon récursive sur N dimensions. La partie dominante vient du tri des sous-tableaux les plus grands :

     
     T(N, M) = O(M^{2N-2})
     

Conclusion

• • La complexité globale est

    [
    O(M^{2N-2})