Algorithmique : tri et complexité

Notions de base — algorithmes, problèmes, complexité

Claire Borrelli

2023-10-01

Plan

  1. Qu’est-ce qu’un algorithme ?
  2. Le problème du tri, trois solutions
  3. Mesurer la complexité d’un algorithme
  4. Notation asymptotique
  5. Comparaison empirique en Python

1. Algorithme, problème, instance

Algorithme

Note

Un algorithme est une procédure bien définie qui prend une entrée, la transforme par une suite d’étapes précises, et produit une sortie.

Un problème décrit ce qu’on veut (la relation entre entrée et sortie attendue), sans dire comment l’obtenir.

Une instance est un cas particulier du problème, avec une entrée concrète.

Exemple — Problème : trier une liste de nombres. Instance : trier [5, 3, 8, 2].

Un problème peut avoir plusieurs algorithmes

Pour un même problème, plusieurs algorithmes peuvent exister — avec des performances très différentes.

C’est exactement le cas du problème du tri, qu’on va utiliser comme fil rouge pour introduire la notion de complexité.

2. Le problème du tri

Formalisation

  • Entrée : une séquence de nombres \(s = [a_1, \dots, a_n]\)
  • Sortie : une permutation \([a'_1, \dots, a'_n]\) de \(s\) telle que \(a'_1 \le a'_2 \le \dots \le a'_n\)

On va comparer trois algorithmes classiques pour résoudre ce problème.

Algorithme 1 : le tri à bulles

Idée : parcourir la liste, comparer chaque paire d’éléments voisins, les échanger s’ils sont dans le mauvais ordre. Répéter jusqu’à ce que la liste soit triée — à chaque passage, le plus grand élément restant “remonte” à sa place, comme une bulle.

def tri_bulles(liste):
    liste = liste.copy()
    n = len(liste)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
    return liste

tri_bulles([5, 3, 8, 2, 9, 1])
[1, 2, 3, 5, 8, 9]

Algorithme 2 : le tri par insertion

Idée : construire la liste triée progressivement, en insérant chaque nouvel élément à la bonne place parmi ceux déjà triés — comme on trierait des cartes à jouer dans sa main.

def tri_insertion(liste):
    liste = liste.copy()
    for i in range(1, len(liste)):
        cle = liste[i]
        j = i - 1
        while j >= 0 and liste[j] > cle:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = cle
    return liste

tri_insertion([5, 3, 8, 2, 9, 1])
[1, 2, 3, 5, 8, 9]

Algorithme 3 : le tri rapide (quicksort)

Idée : choisir un pivot au hasard, séparer la liste en éléments plus petits / plus grands que le pivot, puis répéter récursivement sur chaque sous-liste.

from random import randint

def tri_rapide(liste):
    if len(liste) <= 1:
        return liste
    pivot = liste[randint(0, len(liste) - 1)]
    plus_petits = [x for x in liste if x < pivot]
    egaux = [x for x in liste if x == pivot]
    plus_grands = [x for x in liste if x > pivot]
    return tri_rapide(plus_petits) + egaux + tri_rapide(plus_grands)

tri_rapide([5, 3, 8, 2, 9, 1])
[1, 2, 3, 5, 8, 9]

Combien d’étapes pour chaque algorithme ?

Pour une liste de taille \(n\) :

Algorithme Meilleur cas Pire cas Cas moyen
Tri à bulles \(n(n-1)/2\) \(n(n-1)/2\) \(n(n-1)/2\)
Tri par insertion \(n\) \(n(n-1)/2\) \(n(n-1)/4\)
Tri rapide \(n\log n\) \(n(n-1)/2\) \(\approx 1{,}39\, n\log_2 n\)

À retenir : le tri à bulles fait toujours le même nombre de comparaisons, quel que soit l’ordre initial. Les deux autres s’adaptent aux données — parfois beaucoup plus vite, parfois non.

3. Mesurer la complexité

Pourquoi mesurer la complexité ?

  • Comparer des algorithmes indépendamment du matériel utilisé
  • Anticiper si un algorithme restera utilisable quand les données grossissent
  • Estimer les ressources nécessaires (temps, mémoire) avant d’exécuter

Complexité en temps et en espace

Complexité en temps : combien d’opérations élémentaires l’algorithme effectue-t-il, en fonction de la taille \(n\) de l’entrée ?

Complexité en espace : combien de mémoire supplémentaire l’algorithme utilise-t-il ?

Dans les deux cas, on s’intéresse à la façon dont le coût évolue avec \(n\), pas à sa valeur exacte sur une machine donnée.

Meilleur cas, pire cas, cas moyen

Pour une taille d’entrée fixée, la performance dépend du contenu de l’entrée (déjà triée ? dans le désordre le plus défavorable ?).

  • Pire cas : le coût maximal — c’est la garantie la plus utile en pratique, et le focus habituel de l’analyse de complexité
  • Meilleur cas : le coût minimal
  • Cas moyen : le coût moyen sur une distribution donnée des entrées (utile, mais suppose de connaître cette distribution)

4. Notation asymptotique

La notation \(O\) (grand O)

Note

\(f(n) = O(g(n))\) signifie qu’à partir d’un certain rang, \(f\) est majorée par \(g\) à une constante multiplicative près : il existe \(c > 0\) et \(n_0\) tels que \(f(n) \le c \cdot g(n)\) pour tout \(n \ge n_0\).

C’est un majorant : ça sert typiquement à borner le pire cas.

Les notations \(\Omega\) et \(\Theta\)

  • \(f(n) = \Omega(g(n))\) : \(g\) est un minorant de \(f\) (à constante près)
  • \(f(n) = \Theta(g(n))\) : \(f\) et \(g\) ont le même ordre de grandeur (\(f = O(g)\) et \(f = \Omega(g)\))

Avec ces notations : tri à bulles et tri par insertion sont \(O(n^2)\) dans le pire cas, tri rapide est \(O(n \log n)\) en moyenne mais \(O(n^2)\) dans le pire cas.

5. Comparaison empirique

Mesurer le temps réel d’exécution

Vérifions ces résultats théoriques en pratique, avec des listes aléatoires de tailles croissantes.

import time
import random

def chronometrer(fonction, liste):
    debut = time.perf_counter()
    fonction(liste)
    return time.perf_counter() - debut

tailles = [100, 300, 600, 1000, 1500]
resultats = {"bulles": [], "insertion": [], "rapide": []}

for n in tailles:
    liste = [random.randint(0, 10000) for _ in range(n)]
    resultats["bulles"].append(chronometrer(tri_bulles, liste))
    resultats["insertion"].append(chronometrer(tri_insertion, liste))
    resultats["rapide"].append(chronometrer(tri_rapide, liste))

Visualisation

import matplotlib.pyplot as plt

plt.figure(figsize=(7, 4.5))
for nom, temps in resultats.items():
    plt.plot(tailles, temps, marker="o", label=nom)
plt.xlabel("Taille de la liste (n)")
plt.ylabel("Temps d'exécution (s)")
plt.title("Temps de tri mesuré selon la taille de l'entrée")
plt.legend()
plt.tight_layout()
plt.show()

Interprétation

  • Le tri rapide reste nettement plus rapide que les deux autres à mesure que \(n\) augmente — cohérent avec sa complexité \(O(n\log n)\) contre \(O(n^2)\)
  • Sur de petites listes, la différence est peu visible : les constantes cachées derrière le \(O(\cdot)\) comptent aussi en pratique
  • Ce type de mesure empirique complète l’analyse théorique, sans la remplacer — le pire cas peut toujours arriver sur une entrée défavorable

Conclusion

  • Un même problème peut avoir plusieurs algorithmes aux performances très différentes
  • La complexité s’exprime en fonction de la taille de l’entrée, indépendamment du matériel
  • La notation \(O\) (et \(\Omega\), \(\Theta\)) permet de comparer des algorithmes de façon rigoureuse
  • L’analyse théorique et la mesure empirique se complètent