Complexité,
recherche et tris.

• Dire si un algorithme est en O(1), O(log n), O(n), O(n log n) ou O(n²), et ce que cela implique.
• Écrire une recherche dichotomique correcte, et en justifier la terminaison.
• Écrire trois algorithmes de tri et expliquer pourquoi l’un est fondamentalement meilleur.
• Mesurer proprement et interpréter une courbe de temps.

Parce qu’un ordinateur deux fois plus rapide divise la constante par deux, mais ne change pas la forme de la courbe. Un algorithme O(n²) sur un supercalculateur finira toujours par perdre contre un O(n log n) sur un Raspberry Pi, pour n assez grand. La notation O décrit le comportement asymptotique : ce qui se passe quand n devient grand. En concours, on vous demandera « quelle est la complexité ? » et on attend une justification par comptage, pas une mesure.

log₂(n) est le nombre de fois qu’on peut diviser n par 2 avant d’arriver à 1. log₂(1 000 000) ≈ 20, log₂(10⁹) ≈ 30. Un algorithme en O(log n) qui « coupe en deux » à chaque étape est presque aussi rapide qu’un accès direct. C’est le pouvoir de la dichotomie.

Meilleur : 1 comparaison (la cible est en tête). Pire : n (la cible est en queue ou absente). Moyen : n/2 si elle est présente à une position aléatoire. On raisonne presque toujours sur le pire cas : c’est la garantie. Un robot doit réagir à temps même dans le pire cas. (Le global ici est une facilité pour compter ; en vrai code, on renverrait le compte.)

« Je pense à un nombre entre 1 et 1000 » : avec « plus grand / plus petit », 10 questions suffisent (2¹⁰ = 1024). Chaque question divise l’espace par deux. C’est exactement la dichotomie, et c’est pour cela que le nombre d’étapes est log₂(n). La condition « liste triée » est indispensable : sur une liste en désordre, couper en deux ne dit rien. Trier coûte O(n log n) ; si on cherche souvent, ça vaut le coup.

Tour i : n − i − 1 comparaisons. Total : (n−1) + (n−2) + … + 1 = n(n−1)/2 ≈ n²/2. Que la liste soit déjà triée ou non, le nombre de comparaisons est le même : O(n²) toujours. Avantage : très peu d’échanges (n − 1 au plus), ce qui compte si déplacer un élément est coûteux.

Sur une liste presque triée, l’insertion est linéaire : chaque élément ne se décale que de quelques cases. C’est le cas d’un flux de mesures où seule la dernière valeur est nouvelle. Les bibliothèques réelles (dont celle de Python) utilisent le tri par insertion pour les petits morceaux de moins de 32 éléments, où il bat tout le monde grâce à sa simplicité.

On coupe en deux jusqu’à des listes de 1 élément : log₂(n) niveaux de découpe. À chaque niveau, fusionner tous les morceaux coûte n opérations au total. D’où n × log₂(n). La fonction qui s’appelle elle-même est récursive : c’est le sujet de la séance 12. Le tri fusion est le premier algorithme « diviser pour régner » de l’histoire (von Neumann, 1945), et il est optimal : aucun tri par comparaison ne peut faire mieux que O(n log n) dans le pire cas — un théorème qu’on démontre en prépa avec un argument de comptage sur les n! ordres possibles.

Quand n double : sélection et insertion ×4 (quadratique), fusion ×2 et un peu plus (n log n), sorted pareil mais 50 fois plus vite car écrit en C. Extrapolez : pour n = 1 000 000, la sélection prendrait des heures, la fusion quelques secondes. Refaites la mesure avec une liste déjà triée : l’insertion devient la plus rapide. Il n’y a pas de « meilleur tri » absolu, il y a le bon tri pour les bonnes données.

f1 : O(1) — une formule, quel que soit n. f2 : O(n). f3 : O(n²) — 0 + 1 + … + (n−1) = n(n−1)/2 tours. f4 : O(log n). f5 : O(n log n) — n tours, chacun avec log₂(n) doublements. Les mesures confirment : f1 constant, f2 ×2, f3 ×4, f4 quasi constant, f5 un peu plus que ×2. Notez que f1 et f2 calculent la même chose : la formule de Gauss remplace une boucle. Trouver une formule fermée est la meilleure optimisation possible.

def racine_entiere(n):
    bas, haut = 0, n
    while bas < haut:
        milieu = (bas + haut + 1) // 2     # arrondi vers le haut : évite la boucle infinie
        if milieu * milieu <= n:
            bas = milieu
        else:
            haut = milieu - 1
    return bas

def premier_superieur(liste, seuil):
    bas, haut = 0, len(liste)
    while bas < haut:
        milieu = (bas + haut) // 2
        if liste[milieu] <= seuil:
            bas = milieu + 1
        else:
            haut = milieu
    return bas

10⁹ pour 10¹⁸, 4, 5. L’arrondi vers le haut dans racine_entiere est le détail qui fait tout : avec (bas + haut) // 2 et bas = milieu, on peut boucler sur bas = haut − 1. La deuxième fonction s’appelle bisect_right dans le module bisect : elle sert à insérer dans une liste triée en la gardant triée. Ces deux variantes (« plus grand tel que » / « premier tel que ») couvrent 90 % des usages de la dichotomie.

def tri_rapide(liste):
    if len(liste) <= 1:
        return liste
    pivot = liste[0]
    petits = [x for x in liste[1:] if x < pivot]
    grands = [x for x in liste[1:] if x >= pivot]
    return tri_rapide(petits) + [pivot] + tri_rapide(grands)

Sur une liste triée, le pivot est toujours le minimum : « petits » est vide, « grands » a n − 1 éléments, et on refait n niveaux au lieu de log n → O(n²), et une profondeur de récursion n qui dépasse la limite de Python (~1000). Avec pivot = random.choice(liste), le pire cas devient improbable : O(n log n) en moyenne, quelle que soit l’entrée. Le tri rapide est en pratique le plus rapide des tris (bonne utilisation du cache, séance 01), mais sans garantie de pire cas — contrairement au tri fusion. Les bibliothèques réelles combinent les deux (introsort) ou utilisent Timsort. Question d’oral classique : « quelle est la complexité du tri rapide ? » Réponse attendue : O(n log n) en moyenne, O(n²) au pire, et pourquoi.