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: []int) → bool:
pour chaque i de [1 .. T.longueur[:
si T[i] < T[i-1]:
rendre Faux
rendre Vrai
Tests de Fonctionnement
L'algorithme rend bien :
Vraipourest_trie([42])Fauxpourest_trie([4, 2])Vraipourest_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és de l'algorithme est_trié
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 le 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
Comme on a pas d'information relative à la répartition des nombre du tableau et que seul l'ordre interne des valeurs du tableau importe pour vérifier s'il est trié ou non, on utilise le modèle du tableau aléatoire pour nos calculs de complexité en moyenne.
Sous ce modèle pour $T$, la probabilité pour notre algorithme de reconnaissance fasse exactement :
- 1 itération est $p_1 = {\Pr}[T[0] > T[1]]$ et vaut $1/2$
- 2 itérations est $p_2 = {\Pr}[(T[0] < T[1]) \text{ et } (T[1] > T[2])]$
- ...
- i itérations est $p_i = {\Pr}[(T[0] < T[1]) \text{ et } (T[1] < T[2]) \text{ et } \;\dots\; \text{ et } (T[i-2] < T[i-1]) \text{ et } (T[i-i] > T[i])]$
Les évènements ne sont pas indépendant donc pour $p_2$ on a que :
Mais comme :
et que :
puisque la partie gauche est plus contrainte pour $T[2]$ que la partie de droite (on a la valeur de $T[0]$ qui serait favorable en moins). On en conclut que :
Un raisonnement identique nous permet de minorer $p_i$ :
Comme chaque itération est de complexité $\mathcal{O}(1)$, la complexité en moyenne sous ce modèle de probabilité vaut :
Comme $i \leq (\sqrt{2})^i$ pour tout $i \geq i$ on a :
Et on utilise un résultat qu'on a déjà démontré pour finir la majoration :
On a donc la proposition surprenante suivante (mais qu'on a déjà rencontré lors de la recherche d'un sous-mot) :
Proposition
La complexité en moyenne du problème de la reconnaissance est en temps constant.
Ce résultat est remarquable :
- Pour le problème de la reconnaissance : 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.
Je vois bien dans votre regard que vous ne me croyez pas. Essayez donc par vous même :
Testez le code suivant (chez moi le max était de 4) pour voir que le nombre maximum d'itération est très inférieur à la longueur du tableau (chez moi le max était de 4).
Puis essayez avec des tableaux plus contraints (comme T = 5 * list(range(4)) par exemple) pour voir que c'est toujours vrai si le tableau possède quelques égalités.
from random import shuffle
def compte(T):
for i in range(len(T)-1):
if T[i] > T[i+1]:
return i +1
return len(T) - 1
T = list(range(20))
nb = []
for i in range(100):
shuffle(T)
nb.append(compte(T))
print(nb)
print(max(nb))
On peut aussi comprendre ce résultat remarquant que les tableaux pour lesquels l'algorithme fait exactement $i$ iterations sont ceux pour lesquels :
- le $i+1$ ème élément n'est pas le plus grand
- les $i$ premiers éléments sont triées
Et il y en a très (très) peu : il n'y en a que $i$ tableaux de longueur $i$ sur les $(i+1)!$ possibles qui vérifient cette condition. La probabilité $p_i = \frac{i}{(i+1)!}$ d'en attraper un tend très (très) vite vers 0 :
- $p_1 = \frac{1}{2!} = 0.5$
- $p_2 = \frac{2}{3!} \simeq 0.3$
- $p_3 = \frac{3}{4!} = .1$
- $p_4 = \frac{4}{5!} \simeq 0.003$
- ...
- $p_{9} = \frac{9}{10!} \simeq 2.5 \cdot 10^{-6}$
- ...
- $p_{19} = \frac{19}{20!} \simeq 7.8 \cdot 10^{-18}$
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.