I1 — Algorithmes et complexité

Objectif du chapitre. Apprendre à concevoir des algorithmes (recherche séquentielle et dichotomique, tris par insertion et fusion), à introduire la récursivité (le tri fusion en dépend) et à évaluer la complexité d'un algorithme en grand $O$. Ce chapitre porte les deux capacités exigibles de l'IPT : I1.dichotomie et I1.complexite-algorithme.

Prérequis

Ce chapitre suppose les bases de Python du chapitre I1 — Bases Python et représentation des nombres (variables, boucles, fonctions, listes).

Notions

1. La récursivité (introduction)

Avant d'aborder le tri fusion, il faut comprendre la récursivité : une fonction récursive est une fonction qui s'appelle elle-même pour résoudre un sous-problème plus petit. Deux ingrédients sont indispensables :

1. un cas de base (la condition d'arrêt, sans laquelle la récursion ne s'arrête jamais) ;
2. un pas récursif qui réduit le problème à un cas plus petit (qui doit tendre vers le cas de base).

Exemple : factorielle. $n! = n \times (n-1)!$, avec $0! = 1$.

def factorielle(n):
    if n == 0:          # cas de base
        return 1
    return n * factorielle(n - 1)   # pas récursif : problème plus petit

factorielle(4) déroule en 4 * factorielle(3) = 4 * 3 * factorielle(2) = 4 * 3 * 2 * factorielle(1) = 4 * 3 * 2 * 1 * factorielle(0) = 24. Chaque appel réduit $n$ de 1 jusqu'au cas de base $n = 0$.

Exemple : somme d'une liste (récursif).

def somme(lst):
    if len(lst) == 0:            # cas de base
        return 0
    return lst[0] + somme(lst[1:])   # premier élément + somme du reste

Récursion : cas de base obligatoire

Sans cas de base (ou si le pas récursif ne réduit pas le problème), la récursion ne s'arrête jamais : on épuise la pile d'appels (erreur RecursionError en Python). Il faut toujours vérifier que le pas récursif converge vers le cas de base.

2. Recherche séquentielle et dichotomique

Recherche séquentielle. La recherche séquentielle (linéaire) parcourt la liste élément par élément ; la complexité est $O(n)$ (au pire : $n$ comparaisons) ; elle fonctionne sur une liste non triée.

Recherche dichotomique. La recherche dichotomique (binaire) divise l'intervalle de recherche en deux à chaque itération ; elle exige une liste triée ; la complexité est $O(\log n)$ (au pire : $\lceil \log_2 n \rceil$ comparaisons) ; à chaque étape, on compare l'élément central à la valeur cherchée et on élimine la moitié de l'intervalle.

Exemple (dichotomie).

def recherche_dichotomique(lst, x):
    a, b = 0, len(lst) - 1
    while a <= b:
        m = (a + b) // 2
        if lst[m] == x:
            return m
        elif lst[m] < x:
            a = m + 1
        else:
            b = m - 1
    return -1

La complexité est $O(\log n)$ : pour $n = 10^6$, au plus $\log_2(10^6) \approx 20$ comparaisons (contre $10^6$ pour la recherche séquentielle).

Déroulé pas à pas. Cherchons $x = 23$ dans lst = [2, 5, 8, 12, 16, 23, 38, 45] ($n = 8$) :

Étape	$a$	$b$	$m=(a+b)//2$	lst[m]	Comparaison	Action
1	0	7	3	12	$12 < 23$	$a = 4$ (moitié droite)
2	4	7	5	23	$23 = 23$	trouvé à l'indice 5

En 2 étapes (au lieu de 6 pour la séquentielle), l'algorithme a trouvé 23. À chaque étape, l'intervalle $[a, b]$ est divisé par 2 : c'est pourquoi le nombre d'étapes est $\log_2 n$.

3. Tris : insertion et fusion

Tri par insertion. Le tri par insertion insère chaque élément à sa place dans la partie triée ; la complexité est $O(n^2)$ (au pire) mais $O(n)$ si la liste est déjà triée ; c'est un tri stable (il préserve l'ordre des éléments égaux) et in place.

def tri_insertion(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key
    return lst

Tri fusion (merge sort). Le tri fusion divise la liste en deux moitiés, trie récursivement chaque moitié (récursivité du §1), puis fusionne les deux moitiés triées. La complexité est $O(n \log n)$ toujours (au pire). C'est le premier exemple de récursion utile que l'on utilise :

def tri_fusion(lst):
    if len(lst) <= 1:              # cas de base : liste de 0 ou 1 élément déjà triée
        return lst
    milieu = len(lst) // 2
    gauche = tri_fusion(lst[:milieu])      # tri récursif de la moitié gauche
    droite = tri_fusion(lst[milieu:])      # tri récursif de la moitié droite
    return fusion(gauche, droite)          # fusion des deux moitiés triées

def fusion(g, d):
    res = []
    i = j = 0
    while i < len(g) and j < len(d):
        if g[i] <= d[j]:
            res.append(g[i]); i += 1
        else:
            res.append(d[j]); j += 1
    res.extend(g[i:])   # reste éventuel de g
    res.extend(d[j:])   # reste éventuel de d
    return res

Déroulé pas à pas. Trions [5, 2, 4, 1] :

1. Diviser : [5, 2, 4, 1] → [5, 2] et [4, 1].
2. Diviser : [5, 2] → [5] et [2] ; [4, 1] → [4] et [1].
3. Fusionner (cas de base, listes de 1 élément) : [5]+[2] → [2, 5] ; [4]+[1] → [1, 4].
4. Fusionner : [2, 5]+[1, 4] → comparer $2$ et $1$ (prendre $1$), $2$ et $4$ (prendre $2$), $5$ et $4$ (prendre $4$), reste $[5]$ → [1, 2, 4, 5].

Le tri fusion est stable et en $O(n \log n)$ indépendamment de l'état initial de la liste (contrairement à l'insertion).

Tri rapide (complément). Le tri rapide (quick sort, hors programme) choisit un pivot, partitionne, puis trie récursivement ; la complexité est $O(n \log n)$ en moyenne mais $O(n^2)$ au pire.

4. Complexité des algorithmes

La complexité mesure le nombre d'opérations élémentaires (ou le temps) en fonction de la taille $n$ de l'entrée ; on utilise la notation asymptotique (grand $O$, $\Omega$, $\Theta$) ; les complexités usuelles (de la plus rapide à la plus lente) sont : $O(1)$ (constant), $O(\log n)$ (dichotomie), $O(n)$ (recherche linéaire), $O(n \log n)$ (tri fusion, rapide), $O(n^2)$ (tri insertion, bulles), $O(2^n)$ (récurrence exponentielle), $O(n!)$ (permutations).

Règles. La complexité d'un algorithme séquentiel (blocs successifs) est la somme des complexités ; celle d'une boucle de $k$ itérations avec un corps en $O(f)$ est $O(k \cdot f)$ ; celle d'une récurrence $T(n) = 2T(n/2) + O(n)$ (tri fusion) est $O(n \log n)$ — résolution directe : en déroulant la récurrence, $T(n) = 2^k T(n/2^k) + k\,O(n)$ ; en prenant $k = \log_2 n$ (donc $n/2^k = 1$), $T(n) = n\,T(1) + \log_2 n \cdot O(n) = O(n \log n)$ (le théorème maître — complément — généralise ce calcul) ; on ignore les termes inférieurs et les constantes (la complexité asymptotique caractérise le comportement pour $n \to \infty$).

Exemple. Une fonction avec une boucle de $n$ itérations où chaque itération appelle une recherche dichotomique sur une liste de $n$ éléments : la complexité est $O(n \cdot \log n)$ (la boucle $O(n)$ multipliée par la recherche $O(\log n)$) ; si la recherche était séquentielle ($O(n)$), la complexité serait $O(n^2)$.

Capacités exigibles

• I1.complexite-algorithme — Évaluer la complexité d'un algorithme : identifier les boucles (leur nombre d'itérations en fonction de $n$) et les appels récursifs ; appliquer les règles (blocs successifs : somme ; boucle de $k$ itérations avec corps $O(f)$ : $O(k \cdot f)$ ; récurrence $T(n) = aT(n/b) + O(n^d)$ : théorème maître — complément) ; exprimer la complexité en grand $O$ (en ignorant les termes inférieurs et les constantes) ; comparer les complexités ($O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$) ; justifier le choix d'un algorithme (par exemple dichotomie $O(\log n)$ vs séquentielle $O(n)$).
• I1.dichotomie — Implémenter une recherche dichotomique : vérifier que la liste est triée (sinon la recherche échoue) ; initialiser les bornes $a = 0$ et $b = \text{len}(lst) - 1$ ; itérer tant que $a \leq b$ : calculer le milieu $m = (a + b) // 2$ ; comparer lst[m] à la valeur cherchée $x$ ; si égal, retourner $m$ ; si lst[m] < x, passer à la moitié droite ($a = m + 1$) ; si lst[m] > x, passer à la moitié gauche ($b = m - 1$) ; si la boucle se termine sans trouver $x$, retourner $-1$ ; la complexité est $O(\log n)$.

Ce qui tombe en colle et en DS

• Implémenter une recherche dichotomique et justifier sa complexité $O(\log n)$.
• Évaluer la complexité d'un algorithme donné (identifier boucles et récursions, appliquer les règles).
• Comparer deux algorithmes (dichotomie vs séquentielle, fusion vs insertion) et justifier un choix.

Pièges classiques

• Dichotomie : liste triée : la recherche dichotomique exige une liste triée (sinon elle échoue ou renvoie un résultat faux) ; il ne faut pas l'appliquer à une liste non triée ; si la liste n'est pas triée, il faut d'abord la trier ($O(n \log n)$) puis rechercher ($O(\log n)$) ; la complexité totale est $O(n \log n)$ (dominée par le tri).
• Dichotomie : bornes incluses : la condition de boucle est $a \leq b$ (pas $a < b$) ; il ne faut pas oublier le cas $a = b$ (sinon on manque le dernier élément) ; les mises à jour sont $a = m + 1$ et $b = m - 1$ (pas $a = m$ et $b = m$, sinon boucle infinie) ; le milieu est $m = (a + b) // 2$ (pas $(a + b) / 2$, sinon flottant).
• Complexité : somme vs produit : la complexité d'un algorithme séquentiel (blocs successifs) est la somme des complexités ; celle d'une boucle imbriquée est le produit ; il ne faut pas confondre les deux ; par exemple deux boucles successives de $n$ itérations : $O(n) + O(n) = O(n)$ (pas $O(n^2)$) ; deux boucles imbriquées : $O(n) \times O(n) = O(n^2)$.
• Complexité : constantes ignorées : la complexité asymptotique ignore les constantes et les termes inférieurs ; $O(2n + 5) = O(n)$ ; la complexité caractérise le comportement pour $n \to \infty$ (pas le nombre exact d'opérations).
• Récursion : cas de base : sans cas de base (ou si le pas récursif ne réduit pas le problème), la récursion ne s'arrête jamais (RecursionError) ; il faut toujours vérifier que le pas récursif converge vers le cas de base.
• Tri insertion : pire cas $O(n^2)$ : le tri par insertion a une complexité $O(n^2)$ au pire (liste inversée) mais $O(n)$ si la liste est déjà triée ; le tri fusion a une complexité $O(n \log n)$ toujours (au pire) ; le choix du tri dépend de la taille et de l'état de la liste.

Graphe de référence

Nombre de comparaisons en fonction de la taille $n$ de la liste pour la recherche séquentielle ($n$ comparaisons au pire) et la recherche dichotomique ($\lceil \log_2 n \rceil$ comparaisons au pire) : la courbe séquentielle est linéaire ($n$) ; la courbe dichotomique est logarithmique ($\log_2 n$) ; pour $n = 1000$, la séquentielle fait 1000 comparaisons et la dichotomique en fait 10 ; pour $n = 10^6$, la séquentielle fait $10^6$ comparaisons et la dichotomique en fait 20 ; la dichotomie est beaucoup plus rapide pour les grandes listes.

Pour aller plus loin

Annales utilisables sur ce chapitre : voir la page générale Ressources, exercices et annales pour les manuels recommandés et les banques d'exercices gratuites.