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 et admettent donc un minimum.

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

• 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 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) qui 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. Cette étude nous permettra de voir 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 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 longueur du tableau puisque l'algorithme ci-dessous (dont on on a déjà calculé la complexité) résout le problème

algorithme recherche(T: [entier], x: entier) → booléen:
    pour chaque (e := entier) de T:
        si e == x:
            rendre Vrai
    rendre Faux

Complexité du problème "recherche"

Notre borne minimale de $\mathcal{O}(1)$ semble irréaliste. Supposons en effet 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 : l'algorithme $A$ n'a pas besoin de regarder toutes les cases du tableau de longueur $n$ en entrée pour répondre.

Soit alors un tableau $T$ de longueur $n$ qui ne contient pas x. 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] = x$

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 passé en entrée. Tout algorithme résolvant le problème recherche doit au moins être de complexité $\mathcal{O}(n)$. On peut donc une nouvelle borne minimale pour notre problème : $\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 :

À vous :

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

Le principe de la recherche dichotomique permet de savoir si un entier donné est dans un tableau d'entier trié.

On cherche à savoir si l'entier $x$ est entre les indices $a$ et $b \geq a$ d'un tableau d'entiers $T$. On procède récursivement selon la valeur de $t[\lfloor (a + b)/2 \rfloor]$ :

• si $T[\,\lfloor (a + b)/2 \rfloor\,] = x$ on a trouvé l'élément
• si $T[\,\lfloor (a + b)/2 \rfloor\,] > x$, l'indice recherché est forcément avant $\lfloor (a + b)/2 \rfloor$. On recommence alors la procédure avec :
  • $a = \lfloor (a + b)/2 \rfloor + 1$
  • $b$ inchangé
• si $T[\,\lfloor (a + b)/2 \rfloor\,] < x$, l'indice recherché est forcément après $\lfloor (a + b)/2 \rfloor$. On recommence alors la procédure avec :
  • $a$ inchangé
  • $b' = \,\lfloor (a + b)/2 \rfloor\, - 1$

Ce principe donne l'algorithme suivant :

algorithme recherche_dichotomique(T: [entier], x: entier) → booléen:
  (a := entier) ← 0
  (b := entier) ← T.longueur - 1
  m := entier

  tant que a ≤ b:
      m ← (a + b) // 2  # division entière

      si (t[m] == x):
          rendre Vrai  # m est l'indice
      si (t[m] < x):
          a ← m + 1
      si (t[m] > x):
          b ← m - 1

  rendre Faux

É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 b - a 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 T, alors sa position est plus grande que a et plus petite que b
    2. si l'on sort de la boucle l'invariant est toujours vérifié mais comme a > b, x ne peut être dans T

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, b - a est divisé par 2, il y a autant d'itérations que l'on peut diviser $T.\mbox{\small longueur}$ par 2.

Si $K$ est ce nombre d'itérations, on a que : $2^{K} \leq T.\mbox{\small longueur}$. Il existe un nombre $p$ tel que $2^p \leq T.\mbox{\small longueur} < 2^{p + 1}$. On ne peut donc pas diviser $T.\mbox{\small longueur}$ par 2, ou un nombre plus petit que lui, plus de $p$ fois. Ce nombre est exactement la partie entière de $\log_2(T.\mbox{\small longueur})$ puisque :

On en conclut le théorème fondamental de la dichotomie : le nombre de fois où l'on peut diviser par 2 un nombre $n$ est $\log_2(n)$ : il y a donc au plus $K \leq \log_2(n) + 1$ itérations (avec $n$ la longueur du tableau). Comme $\log_2(n) = \frac{\ln(n)}{\ln(2)}$ on a :

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 recherche : 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 longueur 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 x 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 x n'est pas dans tableau
• soit x est à l'indice 0 du tableau
• soit x est à l'indice 1 du tableau
• ...
• soit x est à l'indice $n-1$ du tableau

En algorithmie, distinguer parmi plusieurs cas se fait par des tests (on utilise l'instruction si (expression) alors: ...). De là :

Comme dans le cas de la recherche 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))$

À vous :