🧮 Algorithmes avancés

O(1)       : constant   — accès tableau par indice
O(log n)   : logarith.  — dichotomie, ABR équilibré
O(n)       : linéaire   — parcours liste
O(n log n) : quasi-lin. — tri fusion, quicksort (moy.)
O(n²)      : quadr.     — tri sélection/insertion

COMPARAISON pour n = 1 000 000 :
O(1)       → 1 opération
O(log n)   → 20 opérations
O(n)       → 1 000 000
O(n log n) → 20 000 000
O(n²)      → 10¹² (inutilisable !)

Règle : préférer O(n log n) à O(n²) dès n > 1000.

Paradigme : DIVISER POUR RÉGNER
Complexité : O(n log n) garanti (pire ET meilleur cas)
Mémoire : O(n) supplémentaire
Stable : ✓ (préserve l'ordre des éléments égaux)

def tri_fusion(lst):
    if len(lst) <= 1:
        return lst
    m = len(lst) // 2
    g = tri_fusion(lst[:m])
    d = tri_fusion(lst[m:])
    return fusionner(g, d)

def fusionner(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
    return res + g[i:] + d[j:]

print(tri_fusion([38, 27, 43, 3]))  # [3, 27, 38, 43]

Paradigme : DIVISER POUR RÉGNER
Complexité : O(n log n) moyen, O(n²) pire cas
Mémoire : O(log n) (récursion)
Pas stable mais très efficace en pratique

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[len(lst) // 2]
    gauche = [x for x in lst if x < pivot]
    milieu = [x for x in lst if x == pivot]
    droite = [x for x in lst if x > pivot]
    return quicksort(gauche) + milieu + quicksort(droite)

print(quicksort([3, 6, 8, 10, 1, 2, 1]))  # [1, 1, 2, 3, 6, 8, 10]

CHOIX DU PIVOT :
Pivot = milieu : bonne heuristique
Pivot aléatoire : évite le pire cas en pratique
Pire cas : liste déjà triée avec pivot=premier