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 :

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 :

  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 :

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 :

Les évènements ne sont pas indépendant donc pour $p_2$ on a que :

$$ p_2 = {\Pr}[(T[0] < T[1]) \text{ et } (T[1] > T[2])] \neq {\Pr}[T[0] < T[1]] \;\cdot\; {\Pr}[T[1] > T[2]] $$

Mais comme :

$$ {\Pr}[(T[0] < T[1]) \text{ et } (T[1] > T[2])] = {\Pr}[(T[0] < T[1])] \;\cdot\; {\Pr}[T[1] > T[2] \;\mid\; T[1] > T[0]] $$

et que :

$$ {\Pr}[T[1] > T[2] \;\mid\; T[1] > T[0]] \leq {\Pr}[T[1] > T[2]] $$

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 :

$$ p_2 \leq {\Pr}[T[0] < T[1]] \;\cdot\; {\Pr}[T[1] > T[2]] = \frac{1}{2} \;\cdot\; \frac{1}{2} = \frac{1}{4} $$

Un raisonnement identique nous permet de minorer $p_i$ :

$$ p_i \leq {\Pr}[T[0] < T[1]] \cdot {\Pr}[T[1] < T[2]]\cdot \;\dots\; \cdot {\Pr}[T[i-2] < T[i-1]]\cdot {\Pr}[ T[i-i] > T[i]] = \frac{1}{2^i} $$

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

$$ \begin{array}{lcl} C_{\text{moy}}(n) &=& \sum\limits_{i=1}^{n-1}(p_i \cdot (i \cdot \mathcal{O}(1)))\\ &\leq& \sum\limits_{i=1}^{n-1}(\mathcal{O}(\frac{i}{2^i})) \\ &\leq& \mathcal{O}(\sum\limits_{i=1}^{n-1}(\frac{i}{2^i})) \end{array} $$

Comme $i \leq (\sqrt{2})^i$ pour tout $i \geq i$ on a :

$$ \begin{array}{lcl} C_{\text{moy}}(n) &\leq& \mathcal{O}(\sum\limits_{i=1}^{n-1}(\frac{1}{\sqrt{2}})^i)\\ \end{array} $$

Et on utilise un résultat qu'on a déjà démontré pour finir la majoration :

$$ \begin{array}{lcl} C_{\text{moy}}(n) &\leq& \mathcal{O}(\sum\limits_{i=1}^{n-1}(\frac{1}{\sqrt{2}})^i)\\ &\leq& \mathcal{O}(\sum\limits_{i=0}^{n-1}(\frac{1}{\sqrt{2}})^i)\\ &\leq& \mathcal{O}(\frac{1}{1-\frac{1}{\sqrt{2}}})\\ &\leq& \mathcal{O}(1) \end{array} $$

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 :

À retenir
  • 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 :

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 :

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.