Bornes théorique de la complexité du problème du tri

Nous allons nous intéresser à la complexité du problème du tri, indépendamment de la connaissance des algorithmes.

Commençons par une remarque d'importance :

À retenir

Si les éléments du tableau à trier sont tous différents, les permutations de celui-ci sont toutes différentes et une seule est la solution au problème "tri".

Par exemple, pour un tableau à trois éléments :

  1. $[1, 2, 3]$
  2. $[1, 3, 2]$
  3. $[2, 1, 3]$
  4. $[2, 3, 1]$
  5. $[3, 1, 2]$
  6. $[3, 2, 1]$

Quelque soit la forme de l'entrée (de 1 à 6), l'algorithme de tri doit rendre la forme 1 : un algorithme de tri doit pouvoir distinguer parmi toutes les permutations d'un tableau où toutes ses valeurs sont deux à deux différentes.

Proposition

Tout algorithme de tri doit pouvoir distinguer parmi $n!$ choix.

preuve

Il y a $n!$ permutations différentes pour un tableau de taille $n$ dont les éléments sont deux à deux différents et une seule de ces permutation est triée.

Borne maximum

Une première borne simple consiste à créer un algorithme qui calcule toutes les $n!$ permutations d'un tableau et vérifie (avec notre algorithme est_trié) pour chacune d'elle si elle est triée.

TBD dire que c;est classique. On énumère toutes les possibilités esi on a un moyen de vérifier rapide.

Permutations

Commençons par trouver toutes les permutations en utilisant l'algorithme suivant :

algorithme permutations_rec(T: []int, i: int):
    si i ≥ T.longueur - 1:
        affiche T
        rendre ∅
    pour chaque j de [i .. T.longueur-1]:
        T[i], T[j] ← T[j], T[i]
        permutations_rec(T, i + 1)
        T[i], T[j] ← T[j], T[i]

algorithme permutations(T: []int):
    mélange_rec(T, 0)

code python

def permutation_rec(T, i):
    if i >= len(T) - 1:
        print(T)
        return
    for j in range(i, len(T)):
        T[i], T[j] = T[j], T[i]
        permutation_rec(T, i + 1)
        T[i], T[j] = T[j], T[i]


def permutations(T):
    permutation_rec(T, 0)

Si j'exécute le code python de l'algorithme avec le tableau [0, 1, 2, 3] en paramètre avec l'instruction permutations(list(range(4))) j'obtiens :

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 2, 1]
[0, 3, 1, 2]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 2, 0]
[1, 3, 0, 2]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 1, 2, 0]
[3, 1, 0, 2]
[3, 2, 1, 0]
[3, 2, 0, 1]
[3, 0, 2, 1]
[3, 0, 1, 2]

Qui correspond bien à toutes les permutation du tableau en entrée. Maintenant que nous sommes convaincu que l'algorithme fonctionne, essayons de le prouver.

TBD à écrire plus précisément

  1. on prouve que le tableau est inchangé.
  2. il ne modifie pas T[:i]
  3. qu'il affiche toutes les permutation de T[i:]

On peut maintenant ajouter notre :

algorithme permutations_rec(T: []int, i: int):
    si i ≥ T.longueur - 1:
        si est_trié(T):
            rendre T
    pour chaque j de [i .. T.longueur-1]:
        T[i], T[j] ← T[j], T[i]
        permutations_rec(T, i + 1)
        T[i], T[j] ← T[j], T[i]

algorithme permutations(T: []int):
    mélange_rec(T, 0)

code python

def tri_rec(T, i):
    if i >= len(T) - 1:
        print(T)
        return
    for j in range(i, len(T)):
        T[i], T[j] = T[j], T[i]
        permutation_rec(T, i + 1)
        T[i], T[j] = T[j], T[i]


def tri(T):
    return tri_rec(T, 0)

Tri maximum

En ne tenant pas compte de l'algorithme permettant de trouver toutes les permutations d'un tableau, il faudrait déjà $\mathcal{O}(n! \cdot n)$ opérations pour toutes les tester (ce qui est trop).

Proposition

Une borne maximum de la complexité du problème du tri d'un tableau à $n$ éléments est $\mathcal{O}(n! \cdot n)$.

Il existe des algorithmes simple de tri que vous avez sûrement déjà vu au cours de votre vie, comme par exemple le tri par selection (que l'on analysera plus tard) dont la complexité est en $\mathcal{O}(n^2)$ opérations avec $n$ la taille du tableau à trier. On en conclut :

Borne minimum

En utilisant la propriété du nombre de cas à distinguer, on en déduit que comme tout algorithme de tri d'un tableau à $n$ élément doit distinguer parmi $n!$ cas :

Proposition

Une borne minimum de la complexité du problème du tri d'un tableau à $n$ éléments est $\Omega(\ln(n!))$.

Pour expliciter ce qu'est $\ln(n!)$, utilisons la propriété suivante :

Proposition

On a :

$$ \ln(n!) = \Theta(n\ln(n)) $$

preuve

On a :

$$ \begin{array}{rcccl} n \cdot (n-1) \cdot \ ...\ \cdot \frac{n}{2} & \leq & n \cdot (n-1) \ ... \ \cdot 1 &\leq& n \cdot \ ...\ \cdot n \\ \frac{n}{2} \cdot \frac{n}{2} \cdot \ ...\ \cdot \frac{n}{2} & \leq & n \cdot (n-1) \ ... \ \cdot 1 &\leq& n \cdot \ ...\ \cdot n \\ \end{array} $$

Ce qui nous donne l'encadrement :

$$ \begin{array}{rcccl} (\frac{n}{2})^{\frac{n}{2}} & \leq & n! &\leq& (n)^{n} \\ \end{array} $$

Qui devient en passant au $\ln$ :

$$ \begin{array}{rcccl} \ln((\frac{n}{2})^{\frac{n}{2}}) & \leq & \ln(n!) &\leq& \ln(n^n) \\ \frac{n}{2}\ln(\frac{n}{2}) &\leq& \ln(n!) &\leq& n\ln(n) \end{array} $$

Poursuivons en remarquant que puisque $\ln(a\cdot x) = \ln(a) + \ln(x)$, on a $\ln(ax) \geq a\cdot \ln(x)$ si $\frac{\ln(a)}{a-1} \geq \ln(x)$, et donc $\ln(n/2) \geq \ln(n)/2$ pour $n \geq 2\ln(2)$. On combine cette inégalité à notre encadrement précédent pour trouver (pour $n \geq 2\ln(2)$) :

$$ \frac{n}{2}(\frac{1}{2}(\ln(n))) \leq \ln(n!) \leq n\ln(n) $$

Ce qui se dérive directement, pour $n \geq 4 \geq 2\ln(2)$, en :

$$\frac{1}{4} \leq \frac{\ln(n!)}{n\ln(n)} \leq 1$$

Enfin, on peut montrer les équivalences de $\mathcal{O}$ :

  • si $g(n)$ est en $\mathcal{O}(\ln(n!))$ il existe $N_0$ et $C$ tel que : $g(n) < C \cdot \ln(n!)$ pour n > $N_0$. On a donc $g(n) < C \cdot \ln(n!) < C \cdot n\ln(n)$ : $g(n)$ est en $\mathcal{O}(n\ln(n))$.
  • si $g(n)$ est en $\mathcal{O}(n\ln(n))$ il existe $N_0$ et $C$ tel que : $g(n) < C \cdot n\ln(n)$ pour n > $N_0$. Pour $N_1 = \max(N_0, 4)$ on a donc $g(n) < C \cdot \ln(n!) < C \cdot 4 \cdot \ln(n!)$ : $g(n)$ est en $\mathcal{O}(\ln(n!))$.

Cet equivalence nous donne finalement la borne minimum courante :

Proposition

Tout algorithme de tri d'une liste à $n$ éléments est en $\Omega(n\ln(n))$ opérations.

Une borne min du problème du "tri" est donc $\mathcal{O}(n\ln(n))$ où $n$ est la taille du tableau en entrée. La partie suivante montrera qu'il existe des algorithmes de tri complexité $\mathcal{O}(n\ln(n))$ (le tri fusion par exemple), on en conclut donc un peu en avance que :

Proposition

La complexité du problème du tri est n $\Theta(n\ln(n))$ opérations.