Reconnaissance d'un tableau trié

Cours/Algorithmie/Problème du tri/Reconnaissance d'un tableau trié

Définissions le problème de décision associé au problème de savoir si OUI ou NON un tableau d'entiers est trié :

Problème de décision

Nom : est trié ?
Entrée : un tableau $T$ d'entiers
Question : $T$ est-il trié de façon croissante ?

Algorithme

Il existe un algorithme très simple pour le résoudre :

algorithme est_trie(T: [entier]) → booléen:
    pour chaque i de [1, T.longueur[:
        si T[i] < T[i-1]:
            rendre Faux
    rendre Vrai

Tests de Fonctionnement

L'algorithme rend bien :

Vrai pour est_trie([42])
Faux pour est_trie([4, 2])
Vrai pour est_trie([2, 4])

Preuve

La finitude de l'algorithme est claire puisqu'il n'y a qu'une boucle for avec autant d'itérations que la taille du tableau passé en paramètre.

La preuve de correction est tout aussi évidente. Si on arrive en ligne 5 c'est que $T[i-1] \leq T[i]$ pour tout $i \in [1, T.\mbox{\small longueur}[$, donc que le tableau est trié.

Proposition

L'algorithme est_trie est une solution au problème "est trié ?"

Complexité

Ligne à ligne :

définition de la fonction $\mathcal{O}(1)$
—
une boucle for de $K$ itérations
un tests de deux valeurs dans un tableau : $\mathcal{O}(1)$
un retour de fonction $\mathcal{O}(1)$
un retour de fonction $\mathcal{O}(1)$

Que l'on sorte par le retour de la ligne 5 ou 6, le complexité est : $\mathcal{O}(k)$.

Cas le pire

Dans le cas le pire, on parcourt tout le tableau, donc :

Proposition

La complexité de l'algorithme est_trie est $\mathcal{O}(n)$ avec $n$ la taille du tableau en entrée.

Cas les meilleur

Dans le cas le meilleur, on s'arrête dès la première itération :

Proposition

La complexité minimale de l'algorithme est_trie est $\mathcal{O}(1)$ avec $n$ la taille du tableau en entrée.

Complexité en moyenne

La question est délicate. Il faut se demander quel est le modèle sous-jacent à notre tableau de nombres. Si on a aucune information sur la répartition des nombres, on a coutume d'utiliser le modèle suivant :

Modèle du Tableau aléatoire

Un tableau $T$ d'entiers de longueur $n$ est aléatoire s'il résulte de la procédure suivante :

on tire une permutation $\sigma$ de $[0, n-1]$ de façon équiprobable (la probabilité de choisir $\sigma$ est $\frac{1}{n!}$)
$T[i] = \sigma(i)$ pour tout $i \in [0, n-1]$

On utilise ce modèle par ce qu'il est simple à mettre en œuvre et à manipuler, tout en possédant de nombreuses propriétés que l'on aimerait avoir pour un tableau de nombres quelconques, comme :

Proposition

Si $T$ est un tableau aléatoire, on a que la probabilité que $T[i] = k$, donc que $T[i]$ soit le $k$ plus petit élément du tableau, vaut :

$$ \mathbb{P}(T[i] = k) = \frac{1}{n} $$

preuve

Parmi les $n!$ permutations de $[0, n-1]$ il y en a $(n-1)!$ telles que $\sigma(i) = k-1$. La probabilité d'obtenir une telle permutation est alors $\frac{(n-1)!}{n!} = \frac{1}{n}$.

Proposition

Si $T$ est un tableau aléatoire :

$$ \mathbb{P}(T[u] > T[v]) = \frac{1}{2} $$

preuve

Prenons $u$ et $v$ deux indices différents du tableau. Pour que $T[u] > T[v]$, il faut que :

$T[u]$ soit le le $n$ème plus petit élément du tableau (plus grand élément) : probabilité $\frac{1}{n}$
$T[u]$ soit le $n-1$ème plus petit élément du tableau (probabilité $\frac{1}{n}$) et que parmi ces tableaux, $T[v]$ ne soit pas le $n$ème plus petit élément (probabilité $\frac{1}{n-1}$) : probabilité $\frac{1}{n}\cdot \frac{1}{n}$
...
$T[u]$ soit le $n-i$ème plus petit élément du tableau (probabilité $\frac{1}{n}$) et que parmi ces tableaux, $T[u]$ ne soit ni le $n$ème, ni $n-1$, ..., ni le $n-i + 1$ plus petit élément (probabilité $\frac{i}{n-1}$) : probabilité $\frac{1}{n}\cdot \frac{i}{n}$
...

En sommant toutes ces probabilités on obtient :

$$ \mathbb{P}(T[u] > T[v]) = \sum_{i=1}^{n-1}\frac{1}{n}\cdot \frac{i}{n-1} = \frac{1}{n(n-1)}\sum_{i=1}^{n-1}i = \frac{1}{2} $$

Lea deux propriétés précédentes nous permettent de voir que pour notre algorithme de reconnaissance, si $T$ est un tableau aléatoire alors la probabilité :

$p_1$ de ne faire que 1 itération est $\mathbb{P}(T[0] > T[1])$ et vaut $1/2$
$p_2$ de ne faire que 2 itérations est $\mathbb{P}(T[0] < T[1], T[1] > T[2])$, donc que $T[:2]$ est trié mais que $T[:3]$ ne l'est pas : cette probabilité vaut $\frac{1}{2!} - \frac{1}{3!}$ (attention, $T[0] < T[1]$ et $T[1] > T[2]$ ne sont pas indépendant, on a donc pas $\mathbb{P}(T[0] < T[1], T[1] > T[2]) = \mathbb{P}(T[0] < T[1])\cdot \mathbb{P}(T[1] > T[2])$)
...
$p_i$ de ne faire que i itérations est la probabilité que $T[:i]$ soit trié mais que $T[:i+1]$ ne le soit pas : : cette probabilité vaut $\frac{1}{i!} - \frac{1}{(i+1)!}$
...
$p_i$ de ne faire que $n$ itérations est la probabilité que $T[:n]$ soit trié mais que $T$ ne le soit pas : : cette probabilité vaut $\frac{1}{(n-1)!} - \frac{1}{n!}$

Comme chaque itération est de complexité $\mathcal{O}(1)$, la complexité en moyenne sous ce modèle de probabilité vaut :

$$ C= \sum_{i=1}^n[p_i \cdot (i \cdot \mathcal{O}(1))] = \sum_{i=1}^{n-1}(\frac{1}{i!} - \frac{1}{(i+1)!}) \cdot \mathcal{O}(i)) = \mathcal{O}(\sum_{i=1}^{n-1}(\frac{i^2}{(i+1)!})) $$

Comme $i^4 \leq (i+1)!$ pour $i \geq 5$ on a que :

$$ C \leq \mathcal{O}(\sum_{i=1}^{n}(\frac{1}{i^2})) = \mathcal{O}(1) $$

On a utilisé le fait, on le démontrera, que :

$$ \lim_{n\to\infty} \sum_{i=1}^n\frac{1}{i^2} = \frac{\pi^2}{6} $$

Ce résultat est remarquable sous (au moins) deux aspects :

la complexité en moyenne est égale à la complexité minimale et est en temps constant !
ce n'est pas parce que la complexité augmente qu'elle en devient forcément infinie.

À retenir

Borner une complexité par une série convergente est un truc utile pour démontrer qu'un algorithme est en temps constant !

Complexité du problème de la reconnaissance

Comme toute case du tableau peut rendre le tableau non trié, on utilise l'argument de la complexité du problème de la "recherche", un algorithme résolvant ce problème doit considérer toutes les cases du tableau et donc une borne min du problème "est trié ?" est $\Omega(n)$ où $n$ est la taille du tableau en entrée. Comme la complexité de est_trie est de $\mathcal{O}(n)$. On en conclut :

Proposition

La complexité du problème "est trié ?" est de $\Theta(n)$ où $n$ est la taille du tableau en entrée.