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é :

Algorithme

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

algorithme est_trie(T: [entier]) → booléen:
    pour chaque (i := entier) 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é.

Complexité

Ligne à ligne :

1. définition de la fonction $\mathcal{O}(1)$
2. —
3. une boucle for de $K$ itérations
4. un tests de deux valeurs dans un tableau : $\mathcal{O}(1)$
5. un retour de fonction $\mathcal{O}(1)$
6. 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 :

Cas les meilleur

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

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

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 :

Comme les valeurs d'un tableau aléatoires sont deux à deux différentes, la proposition précédente peut s'interpréter aussi comme :

Enfin, dernière propriété qui va être utile dans les calculs :

Ce modèle véhicule de nombreuse propriété l'on aimerait avoir pour un tableau de nombres quelconques :

Calcul de la complexité

Les propriétés précédentes nous permettent de voir que si $T$ est un tableau aléatoire alors 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 :

Or la série des $\sum_{i=1}^{n}(\frac{i}{2^i})$ est toujours plus petite que 2 (on le démontrera) donc :

On a donc la proposition surprenante suivante :

Ce résultat est remarquable :

Notez que l'on a utilisé un majorant des $p_i$ pour que le calcul soit aisé, mais on peut très bien calculer la valeur exacte de $p_i$ en comptant le nombre de tableaux où ces conditions sont vérifiées. Ce sont exactement les tableaux où :

• le $i+1$ ème élément n'est pas le plus grand
• les $i$ premiers éléments sont triées

Pour des tableaux de longueur $i$ il n'y a que $i$ tableaux possibles sur les $(i+1)!$ possibles pour une probabilité de $\frac{i}{(i+1)!}$. Le raisonnement est identique si on ne considère que les $i+1$ premiers éléments de tout tableau et donc $p_i = \frac{i}{(i+1)!}$ pour tout tableau de longueur $n\geq i+1$. On obtient alors :

Comme $i^2 \leq i(i+1)$ on a que :

La série $\sum_{i=0}^{n-2}(\frac{1}{(i)!})$ converge vers $e$ ($e^x = \sum_{i=0}^{+\infty}(\frac{x^i}{i!})$ pour tout réel $x$) donc comme précédemment $C_\text{moy}(n) = \mathcal{O}(1)$

Vérification expérimentale

Je vois bien dans votre regard que vous ne me croyez pas. Essayez donc par vous même :

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))

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 :