Complexité d'un problème algorithmique

Un problème algorithmique est une question solvable par un algorithme. Un même problème peut cependant avoir plusieurs algorithmes solutions, certains étant meilleurs que d'autres. On peut alors se poser la question de la complexité d'un problème algorithmique. C'est à dire :

Cette complexité existe toujours car :

1. le problème étant algorithmique il admet au moins un algorithme pour le résoudre.
2. Les algorithmes résolvant le problème peuvent être classées selon leurs complexités, entières, et admettent donc un minimum.

Mais elle peut être difficile à trouver il faut pouvoir raisonner sans avoir tous les algorithmes (une infinité) à sa disposition.

Cependant, si l'on possède déjà un algorithme pour résoudre le problème, sa complexité est une borne maximale de la complexité du problème qu'il résout. Il est également souvent facile de se donner une borne minimale de la complexité du problème (même si l'on ne sait pas s'il existe un algorithme pour le résoudre), c'est la taille de la sortie de l'algorithme. On a lors l'encadrement :

Cet encadrement est général pour tout problème algorithmique et s'écrit :

Si on arrive à mettre la même valeur à gauche et à droite on aura trouvé la complexité du problème :

Nous illustrerons ici cette problématique avec l'exemple de la recherche d'un élément dans un tableau qui permet d'illustrer plusieurs facettes de ce qu'est un problème algorithmique.

Exemple : recherche d'un élément dans un tableau

On va chercher à résoudre le problème de décision suivant :

Ce qu'on peut déjà dire de notre problème :

• une borne minimale : $\mathcal{O}(1)$ puisque la taille la sortie est un booléen
• une borne maximale : $\mathcal{O}(n)$ où $n$ est la taille du tableau puisque l'algorithme ci-dessous (dont on on a déjà calculé la complexité) résout le problème

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

Complexité du problème "recherche"

Notre borne minimale de $\mathcal{O}(1)$ semble irréaliste. Supposons de façon plus générale qu'il existe un algorithme $A$ qui résout le problème de recherche pour tous les tableaux de longueur $n$ en prenant strictement moins de $n$ instructions : ceci signifie l'algorithme $A$ n'a pas besoin de regarder toutes les cases d'un tableau de longueur $n$ pour répondre.

Soit alors un tableau $T$ de taille $n$ qui ne contient pas valeur. Notre algorithme va répondre NON à la question "est-ce que valeur est dans $T$ ?" en strictement moins de $n$ instructions. Ceci signifie qu'il existe une case du tableau, disons $T[i^\star]$, que l'algorithme n'a jamais regardé lors de son exécution : il ne sait pas ce que contient cette case.

On crée alors un tableau $T'$ de $n$ cases tel que :

• $T'[i] = T[i]$ si $i \neq i^\star$
• $T'[i^\star] = \mbox{valeur}$

Comme $T$ et $T'$ sont identiques sauf pour la case d'indice $i^\star$, si l'algorithme ne regarde pas la case $T[i^\star]$ lors de son exécution pour $T$, il ne regardera pas non plus la case $T'[i^\star]$ lors de son exécution pour $T'$. Il ne pourra donc répondre que la même chose pour $T$ et $T'$, ce qui est impossible puisque la réponse est NON pour $T$ et OUI pour $T'$.

Notre hypothèse était fausse : un algorithme qui résout le problème de la recherche doit accéder au moins une fois à toutes les cases du tableau, il doit au moins être de complexité $\mathcal{O}(n)$ : la complexité du problème de la recherche est en $\Omega(n)$.

Au final on a :

• une borne minimale de la complexité de la recherche de $\Omega(n)$
• un algorithme qui résout le problème en $\mathcal{O}(n)$

Donc :

On peut en déduire une règle générale de la complexité d'un problème :

Cas particulier des tableaux ordonnés

Un cas particulier courant de recherche est le problème :

Le problème "recherche ordonnée" est un sous problème de "recherche", on a donc une borne maximale de $\mathcal{O}(n)$ (où $n$ est la taille du tableau) pour le résoudre puisqu'il suffit d'utiliser l'algorithme est_dans_tableau(T).

Cependant, on utilise souvent un autre algorithme : la recherche dichotomique.

Algorithme de la recherche dichotomique

def recherche_dichotomique(valeur, tableau_trie):
    debut = 0
    fin = len(tableau_trie) - 1

    while fin - debut >= 0:
        milieu = (fin + debut) // 2

        if tableau_trie[milieu] == valeur:
            return True
        elif tableau_trie[milieu] < valeur:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return False

Étudions l'algorithme :

• fonctionnement. On vérifie que pour :
  • un tableau [1, 3, 7] l'algorithme trouve bien 7 et ne trouve pas 8
  • un tableau [1, 3, 3, 7] l'algorithme trouve bien 7 et ne trouve pas 9
• preuve :
  • finitude. La quantité entière fin - debut décroît strictement à chaque itération, elle sera donc strictement négative après un nombre fini d'opération et l'algorithme s'arrêtera.
  • preuve.
    1. on montre trivialement l'invariant de boucle suivant: si valeur est dans tableau_trie, alors sa position est plus grande que debut et plus petite que fin
    2. si l'on sort de la boucle l'invariant est toujours vérifié mais comme debut > fin, valeur ne peut être dans tableau_trie

Les remarques ci-dessus prouvent que l'algorithme recherche_dichotomique résout bien le problème "recherche ordonnée".

Étudions sa complexité. Ligne à ligne :

1. initiation de la fonction $\mathcal{O}(1)$
2. affection : $\mathcal{O}(1)$
3. affection : $\mathcal{O}(1)$
4. —
5. boucle de $K$ itérations (pour l'instant, la valeur de $K$ est inconnue)
6. affection : $\mathcal{O}(1)$
7. —
8. test d'une valeur dans un tableau : $\mathcal{O}(1)$
9. retour de fonction : $\mathcal{O}(1)$
10. test d'une valeur dans un tableau : $\mathcal{O}(1)$
11. addition plus une affectation : $\mathcal{O}(1)$
12. —
13. soustraction plus une affectation : $\mathcal{O}(1)$
14. retour de fonction : $\mathcal{O}(1)$

Ce qui donne comme complexité :

Comme à chaque itération, fin - debut est divisé par 2 : il y a donc au plus $K \leq \log_2(n)$ itérations (avec $n$ la taille du tableau) :

Complexité du problème "recherche ordonnée"

L'algorithme de la recherche dichotomique résout le problème de la "recherche ordonnée" de façon bien plus efficace que l'algorithme est_dans_tableau : il n'a pas besoin de connaître toutes les cases du tableau pour répondre à la question car le tableau est trié. Une borne maximum de la complexité du problème "recherche ordonnée" est alors $\mathcal{O}(\ln(n))$ (avec $n$ la taille du tableau).

Nous allons montrer que l'on ne peut pas faire mieux en montrant que $\mathcal{O}(\ln(n))$ est une borne minimum de notre problème.

Commençons par remarquer que valeur peut se trouver à chaque position du tableau. Tout algorithme qui résout "recherche ordonnée" doit ainsi réussir à distinguer parmi $n + 1$ cas :

• soit valeur n'est pas dans tableau
• soit valeur est à l'indice 0 du tableau
• soit valeur est à l'indice 1 du tableau
• ...
• soit valeur est à l'indice $n-1$ du tableau

En algorithmie, distinguer parmi plusieurs cas se fait par des tests (on utilise les opérations si alors sinon). De là :

• s'il y a 0 test, un algorithme ne peut pas distinguer de cas.
• s'il y a 1 test, un algorithme peut distinguer au plus 2 cas :
  • 1 cas si le test est vrai
  • 1 cas si le test est faux
• s'il y a 2 tests, un algorithme peut distinguer au plus $2 \cdot 2 = 4$ cas :
  • 1 cas si les deux tests sont vrai
  • 1 cas si le premier test est vrai et le second test faux
  • 1 cas si le premier test est faux et le second test vrai
  • 1 cas si les deux tests sont faux
• s'il y a 3 tests, un algorithme peut distinguer au plus $2 \cdot 2 \cdot 2 = 2^3 = 8$ cas :
  • 1 cas si les trois tests sont vrai
  • 1 cas si les deux premiers tests sont vrai et le troisième test faux
  • ...
  • 1 cas si les trois tests sont faux
• ...
• s'il y a $K$ tests, un algorithme peut distinguer au plus $2^K$ cas

On a alors la propriété suivante :

Comme il y a $n+1$ cas au moins à traiter, notre algorithme sera de complexité $\Omega(\ln(n + 1)) = \Omega(\ln(n))$ opérations.

Au final, le problème de la "recherche ordonnée" pour un tableau à $n$ éléments :

• une borne minimale de complexité égal à $\Omega(\ln(n))$
• la complexité de l'algorithme recherche_dichotomique est en $\mathcal{O}(\ln(n))$