Diviser pour régner

Pour calculer $x^n$, l'approche naïve effectue $n-1$ multiplications. En remarquant que $x^n=(x^{n/2}{)}^2$ si $n$ est pair, on divise l'exposant par deux à chaque étape.

def puissance(x, n):
    if n == 0:              # cas de base
        return 1
    demi = puissance(x, n // 2)   # diviser + regner
    if n % 2 == 0:
        return demi * demi        # combiner
    else:
        return demi * demi * x

Le nombre de multiplications passe ainsi de $O(n)$ à $O(\log n)$.

def recherche_dichotomique(tab, cible):
    g, d = 0, len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == cible:
            return m
        elif tab[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return -1   # cible absente

La fonction renvoie l'indice de cible, ou $-1$ si elle est absente.

La version récursive met en évidence la structure « diviser pour régner ».

def rech_dicho(tab, cible, g, d):
    if g > d:
        return -1            # cas de base : zone vide
    m = (g + d) // 2
    if tab[m] == cible:
        return m
    elif tab[m] < cible:
        return rech_dicho(tab, cible, m + 1, d)   # moitie droite
    else:
        return rech_dicho(tab, cible, g, m - 1)   # moitie gauche

La recherche dichotomique sur un tableau de taille $n$ s'effectue en $O(\log n)$ comparaisons dans le pire cas, contre $O(n)$ pour la recherche séquentielle. En effet, à chaque étape la taille de la zone de recherche est divisée par deux : après $k$ étapes il reste environ $n/2^k$ éléments, et le processus s'arrête lorsque $n/2^k\approx 1$, soit $k\approx {\log }_{2}n$.

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

def tri_fusion(tab):
    if len(tab) <= 1:           # cas de base
        return tab
    milieu = len(tab) // 2
    gauche = tri_fusion(tab[:milieu])   # diviser + regner
    droite = tri_fusion(tab[milieu:])
    return fusion(gauche, droite)       # combiner

Le tri fusion d'un tableau de taille $n$ s'effectue en $O(n\log n)$ comparaisons dans tous les cas (meilleur, moyen et pire). En notant $C(n)$ le coût du tri, on a la relation

$$C(n)=2C(n/2)+O(n),$$

où le terme $O(n)$ correspond à la fusion. La récursion comporte ${\log }_{2}n$ niveaux, et chaque niveau effectue un travail total de $O(n)$ : d'où le coût $O(n\log n)$. Le tri fusion est stable mais nécessite un espace mémoire supplémentaire en $O(n)$.

Un tri est dit stable s'il préserve l'ordre relatif des éléments de même clé. Grâce au test a[i] <= b[j] (qui privilégie la liste de gauche en cas d'égalité), le tri fusion est stable.

La version suivante, lisible mais non « en place », utilise des listes en compréhension.

def tri_rapide(tab):
    if len(tab) <= 1:           # cas de base
        return tab
    pivot = tab[0]
    petits = [x for x in tab[1:] if x <= pivot]   # diviser
    grands = [x for x in tab[1:] if x > pivot]
    return tri_rapide(petits) + [pivot] + tri_rapide(grands)

def partition(tab, g, d):
    pivot = tab[d]
    i = g - 1
    for j in range(g, d):
        if tab[j] <= pivot:
            i += 1
            tab[i], tab[j] = tab[j], tab[i]
    tab[i + 1], tab[d] = tab[d], tab[i + 1]
    return i + 1

def tri_rapide_place(tab, g, d):
    if g < d:
        p = partition(tab, g, d)
        tri_rapide_place(tab, g, p - 1)
        tri_rapide_place(tab, p + 1, d)

Le tri rapide d'un tableau de taille $n$ a une complexité :

• en moyenne $O(n\log n)$, lorsque le pivot partage régulièrement le tableau en deux parties équilibrées ;
• dans le pire cas $O(n^2)$, lorsque le pivot est systématiquement le plus petit ou le plus grand élément (par exemple sur un tableau déjà trié si l'on choisit toujours le premier élément comme pivot).

Le choix d'un pivot aléatoire ou de la médiane de trois éléments rend le pire cas très improbable. Le tri rapide trie en place avec un faible surcoût mémoire, ce qui le rend souvent plus rapide en pratique que le tri fusion.

Le paradigme « diviser pour régner » améliore nettement la complexité par rapport aux approches naïves :

Pour $n=1000000$, un tri en $O(n^2)$ demande de l'ordre de $10^{12}$ opérations, alors qu'un tri en $O(n\log n)$ n'en demande qu'environ $2\times 10^7$ : le gain est colossal.

import random, time

def tri_insertion(tab):       # approche naive en O(n^2)
    for i in range(1, len(tab)):
        cle = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j -= 1
        tab[j + 1] = cle

donnees = [random.randint(0, 10000) for _ in range(5000)]

t0 = time.time(); tri_insertion(donnees[:]); t1 = time.time()
t2 = time.time(); tri_fusion(donnees[:]);    t3 = time.time()
print("insertion :", t1 - t0, "s")
print("fusion    :", t3 - t2, "s")

Sur quelques milliers d'éléments, l'écart de temps mesuré illustre concrètement la différence entre $O(n^2)$ et $O(n\log n)$.