Complexité en moyenne

Lorsque le nombre d'opérations d'un algorithme dépend non seulement de la taille de ses entrées mais également de la structure de celles-ci, on a coutume de calculer sa complexité en moyenne :

Cette mesure est très utile en pratique car si la complexité maximale et minimale d'un algorithme est très différente, cela permet de savoir le nombre d'opérations espéré pour un tableau quelconque de taille donné.

Calcul de la complexité en moyenne

Soit $A$ un algorithme dont on veut calculer sa complexité par rapport à la taille $n$ de ses données. Si $\mathcal{E}$ est l'ensemble contenant toutes ses entrées de taille $n$ et s'il faut $N(e)$ opérations pour exécuter l'algorithme $A$ avec l'entrée $e$, on a que :

• la complexité $C_\max(n)$ de l'algorithme vaut $C_\max(n) = \max \{N(e) \mid e \in \mathcal{E}\}$
• la complexité minimum $C_\min(n)$ de l'algorithme vaut $C_\min(n) = \min \{N(e) \mid e \in \mathcal{E}\}$

L'espérance de la complexité, c'est à dire la complexité attendue ou normale si l'algorithme est exécutée pour une entrée au hasard, est appelée complexité en moyenne.

Elle dépend des entrées de celui-ci et plus précisément du nombre de fois où une entrée donnée peut être choisie. Pour pouvoir la calculer de façon formelle, il faut connaître ainsi le modèle probabiliste associé aux données :

Si l'on a pas de modèle a priori, on considérera que chaque donnée est équiprobable : chaque entrée a la même probabilité d'être choisie, $p_e = \frac{1}{\vert \mathcal{E} \vert}$.

Exemple de la recherche d'un élément dans un tableau

Reprenons l'exemple de la recherche d'un élément d'un un tableau :

def est_dans_tableau(valeur, tableau):
    for x in tableau:
        if x == valeur:
            return True
    return False

On avait déterminé ses complexités par rapport à la taille $n$ du tableau :

• la complexité maximale de l'algorithme est_dans_tableau est $\mathcal{O}(n)$ (on parcourt tout le tableau sans trouver valeur)
• la complexité minimale de l'algorithme est_dans_tableau est $\mathcal{O}(1)$ (valeur est le premier élément du tableau)

Si l'on note $\mathcal{E}$ l'ensemble de tous les tableau de taille $n$, il y en a une infinité. Notre calcul de la complexité en moyenne est donc ardu. Pour simplifier le problème, analysons la complexité selon l'endroit où se trouve valeur dans le tableau :

• si valeur est à l'indice $0$ du tableau, il faudra $\mathcal{O}(1)$ opération pour exécuter l'algorithme
• si valeur est à l'indice $1$ du tableau, il faudra deux fois plus d'opérations que s'il était à l'indice $0$, donc $2 \cdot \mathcal{O}(1)$ opérations pour exécuter l'algorithme
• si valeur est à l'indice $2$ du tableau, il faudra trois fois plus d'opérations que s'il était à l'indice $0$, donc $3 \cdot \mathcal{O}(1)$ opérations pour exécuter l'algorithme
• ...
• si valeur est à l'indice $i$ du tableau, il faudra $i+1$ fois plus d'opérations que s'il était à l'indice $0$, donc $(i+1) \cdot \mathcal{O}(1)$ opérations pour exécuter l'algorithme
• ...
• si valeur est à l'indice $n-1$ du tableau, il faudra $n$ fois plus d'opérations que s'il était à l'indice $0$, donc $n \cdot \mathcal{O}(1)$ opérations pour exécuter l'algorithme
• si valeur n'est pas dans le tableau, il faudra $n+1$ fois plus d'opérations que s'il était à l'indice $0$, donc $(n+1) \cdot \mathcal{O}(1)$ opérations pour exécuter l'algorithme

L'ensemble $\mathcal{E}$ de tous les tableaux de taille $n$ peut alors se segmenter en $n+1$ ensembles :

• les ensembles $\mathcal{E}_i$, pour $0 \leq i < n$, qui regroupent les tableaux contenant valeur en position $i$
• l'ensemble $\mathcal{E}_n$, qui regroupe tous les tableaux ne contenant pas valeur

La complexité en moyenne s'écrit alors :

On note $p_{i}$ la probabilité qu'à un tableau d'être dans $\mathcal{E}_i$ :