← Retour à la page de la matière

Cours 2 : Tri et Complexité Algorithmique

1. Tri par sélection (Selection Sort)

1.1 Principe

Le tri par sélection consiste à parcourir un tableau pour trouver l’élément maximal (ou minimal) et le placer à sa position correcte. On répète l’opération pour tous les éléments du tableau.

1.2 Algorithme

void selectionSort(int tab[], int n){
    int temp = 0;
    int indMax = 0;
    for(int i = 0; i < n-1; i++){
        indMax = 0;
        for(int j = 1; j < n-i; j++){
            if(tab[j] > tab[indMax]){
                indMax = j;
            }
        }
        if(indMax != n-1-i){
            temp = tab[indMax];
            tab[indMax] = tab[n-1-i];
            tab[n-1-i] = temp;
        }
    }
}

1.3 Analyse de la complexité

• Taille de l’instance : \(n\) éléments.
• Pire cas :
  • Boucle interne (\(j\)) : \(6(n-1-i)\) opérations par itération de \(i\).
  • Boucle externe (\(i\)) : \(\sum_{i=0}^{n-2} (6(n-1-i) + 13) = 3n^2 + 10n\) opérations.
  • Opérations initiales : 6
  • Total : \(3n^2 + 10n + 6\)
• Meilleur cas :
  • Boucle interne (\(j\)) : 3 opérations par itération de \(i\).
  • Boucle externe (\(i\)) : \(\sum_{i=0}^{n-2} (3(n-1-i) + 7) = \frac{3}{2}n^2 + \frac{5}{2}n\)
  • Opérations initiales : 6
  • Total : \(\frac{3}{2}n^2 + \frac{5}{2}n + 6\)

Conclusion : Le tri par sélection est quadratique dans tous les cas : \(O(n^2)\).

2. Tri par insertion (Insertion Sort)

2.1 Principe

Le tri par insertion consiste à prendre chaque élément du tableau et l’insérer à sa position correcte parmi les éléments déjà triés.

2.2 Algorithme

void insertionSort(int tab[], int size){
    int temp = 0;
    int index = 0;
    for(int i = 1; i < size; i++){
        index = i;
        while(index > 0 && tab[index-1] > tab[index]){
            temp = tab[index-1];
            tab[index-1] = tab[index];
            tab[index] = temp;
            index--;
        }
    }
}

2.3 Exemple d’exécution

Tableau : |3|1|4|2|5|

• Itération 1 (i=1) : 1 est placé avant 3 → |1|3|4|2|5|
• Itération 2 (i=2) : 4 reste en place → |1|3|4|2|5|
• Itération 3 (i=3) : 2 est inséré → |1|2|3|4|5|
• Itération 4 (i=4) : 5 reste en place → |1|2|3|4|5|

2.4 Analyse de la complexité

• Boucle while (lignes 6-10) : \(7i\) opérations par itération (2 tests, 1 &&, 3 affectations, 1 décrémentation)
• Boucle for (ligne 4) : size-1 itérations
• Complexité totale : \(\sum_{i=1}^{size-1} (7i+3) = 3(size-1) + 7\frac{size(size-1)}{2} = O(n^2)\)
• Pire cas : tableau inversé → \(O(n^2)\)
• Meilleur cas : tableau déjà trié → \(O(n)\)

3. Notations de complexité (Landau)

3.1 Notation O (Big O)

Borne supérieure asymptotique :

\(O(g(n)) = \{ f(n) \mid \exists c>0, n_0 \in \mathbb{N}, \forall n \ge n_0, 0 \le f(n) \le c g(n) \}\)

Exemples :

• \(10n + 5 = O(n)\)
• \(n^2 + 2n = O(n^2)\)
• \(2n^3 + 5n^2 = O(n^3)\)

3.2 Notation Ω (Big Omega)

Borne inférieure asymptotique :

\(\Omega(g(n)) = \{ f(n) \mid \exists c>0, n_0 \in \mathbb{N}, \forall n \ge n_0, f(n) \ge c g(n) \}\)

Exemples :

• \(n^2 = \Omega(n)\)
• \(10n^3 + 5n^2 + n = \Omega(n^3)\)

3.3 Notation Θ (Big Theta)

Croissance exacte asymptotique :

\(\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))\)

Exemples :

• Tri par sélection : \(\Theta(n^2)\)
• Tri par insertion (meilleur cas) : \(\Theta(n)\)
• Tri par insertion (pire cas) : \(\Theta(n^2)\)

4. Catégories usuelles de complexité

5. Propriétés utiles de O

Propriétés des notations O

1. Constante
   \(\lambda = O(1)\)
   Toute constante est de complexité constante.
2. Identité
   \(f(n) = O(f(n))\)
   Une fonction est toujours majorée par elle-même.
3. Addition
   \(O(f(n)) + O(g(n)) = O(f(n) + g(n))\)
   La somme de deux fonctions est majorée par la somme de leurs bornes supérieures.
4. Maximum (ou composition)
   \(O(f(n) \circ g(n)) = O(\max(f(n), g(n)))\)
   Lorsque l’on prend le maximum ou une composition élémentaire, la complexité est dominée par la plus grande des fonctions.
5. Multiplication
   \(O(f(n)) \times O(g(n)) = O(f(n) \cdot g(n))\)
   Le produit de deux fonctions est majoré par le produit de leurs complexités.
6. Multiplication par une constante
   \(O(\lambda \cdot f(n)) = O(f(n))\)
   Multiplier une fonction par une constante ne change pas sa complexité asymptotique.