Complexité d'un problème algorithmique

Cours/Algorithmie/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 :

Définition

La complexité (maximale) d'un problème algorithmique est la complexité (maximale) du meilleur algorithme (celui de complexité a plus faible) qui le résout.

Cette complexité existe toujours car :

le problème étant algorithmique il admet au moins un algorithme pour le résoudre.
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 :

Ω (taille sortie) = complexité du problème = O (complexité d’un algorithme le résolvant)

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

Ω (borne minimale du problème) = complexité du problème = O (borne maximale du problème)

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

À retenir

Si l'on arrive à encadrer le problème à gauche par un $Ω$ et à droite par un $O$ avec le même algorithme :

$Ω (complexité de l’algorithme A le résolvant) = complexité du problème = O (complexité de l’algorithme A le résolvant)$

on aura trouvé la complexité du problème : $Θ (complexité de l’algorithme A le résolvant)$ .

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 :

Problème de décision

nom : recherche
données : une valeur et un tableau d'entiers
question : valeur est-elle présente dans le tableau ?

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

une borne minimale : $O (1)$ puisque la taille la sortie est un booléen
une borne maximale : $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

algorithme recherche(t: [entier], x: entier):
    pour chaque e de t:
        si e == x:
            rendre Vrai
    rendre Faux

Complexité du problème "recherche"

Notre borne minimale de $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^{⋆}]$ , 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^{⋆}$
$T^{'} [i^{⋆}] = valeur$

Comme $T$ et $T^{'}$ sont identiques sauf pour la case d'indice $i^{⋆}$ , si l'algorithme ne regarde pas la case $T [i^{⋆}]$ lors de son exécution pour $T$ , il ne regardera pas non plus la case $T^{'} [i^{⋆}]$ 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é $O (n)$ : la complexité du problème de la recherche est en $Ω (n)$ .

Ca ne veut pas dire qu'il n'existe pas des instances où l'algorithme va plus vite (si valeur est le 1er élément du tableau par exemple), mais que pour toute taille $n$ du tableau, il existe des tableaux pour lesquels on est obligé de vérifier toutes les cases (si valeur n'est pas dans tableau).

Au final on a :

une borne minimale de la complexité de la recherche de $Ω (n)$
un algorithme qui résout le problème en $O (n)$

Donc :

Proposition

La complexité du problème de la recherche est en $O (n)$ où $n$ est la taille du tableau.

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

À retenir

Si les données n'ont pas de structure particulière — très souvent — la complexité d'un problème est au moins égale à la taille de ses données.

Si ce n'est pas vrai, c'est que notre problème est vraisemblablement mal posé et qu'on peut se passer de certaines entrées.

Cas particulier des tableaux ordonnés

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

Problème de décision

nom : recherche ordonnée
données : une valeur et un tableau d'entiers triés par ordre croissant
question : valeur est-elle présente dans le tableau ?

Le problème "recherche ordonnée" est un sous problème de "recherche", on a donc une borne maximale de $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

On reprend l'algorithme récursif du calcul dichotomique sous la forme récursive terminale et on le transcrit en algorithme itératif :

algorithme recherche_dichotomique(t: [entier], v: entier) → entier:
  a ← 0
  b ← t.longueur - 1
  si b > a:
  tant que a ≤ b:
    m ← (a + b) // 2  # division entière

    si (t[m] == v):
        rendre m
    si (t[m] < v):
        a ← m + 1
    si (t[m] > v):
        b ← m - 1

  rendre -1

É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, v 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 :

initiation de la fonction $O (1)$
affection : $O (1)$
affection : $O (1)$
—
boucle de $K$ itérations (pour l'instant, la valeur de $K$ est inconnue)
affection : $O (1)$
—
test d'une valeur dans un tableau : $O (1)$
retour de fonction : $O (1)$
test d'une valeur dans un tableau : $O (1)$
addition plus une affectation : $O (1)$
—
soustraction plus une affectation : $O (1)$
retour de fonction : $O (1)$

Ce qui donne comme complexité :

\begin{array}{lcl} C (n) & = & 3 \cdot O (1) + \\ K \cdot (6 \cdot O (1)) + \\ O (1) \\ = & O (K) \end{array}

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

Proposition

L'algorithme recherche_dichotomique résout le problème "recherche ordonnée" en $O (\ln (n))$ (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 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 $O (\ln (n))$ (avec $n$ la taille du tableau).

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

Remarquez bien que la preuve que l'on a donné pour la complexité de "recherche" ne fonctionne pas dans le cas de "recherche ordonnée". On ne peut pas fabriquer comme précédemment de tableau $T^{'}$ car les valeurs doivent être ordonnées.

Commençons par remarquer que v 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 v n'est pas dans tableau
soit v est à l'indice 0 du tableau
soit v est à l'indice 1 du tableau
...
soit v 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 :

À retenir

Si un algorithme doit distinguer parmi $n$ cas, il devra posséder au moins $\log_{2} (n)$ tests. Sa complexité sera ainsi en $Ω (\ln (n))$

Comme il y a $n + 1$ cas au moins à traiter, notre algorithme sera de complexité $Ω (\ln (n + 1)) = Ω (\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 à $Ω (\ln (n))$
la complexité de l'algorithme recherche_dichotomique est en $O (\ln (n))$

Proposition

La complexité du problème de la "recherche ordonnée" est en $Θ (\ln (n))$ où $n$ est la taille du tableau.