6.2. Complexité

6.2.1. Définition générale

L’analyse de la complexité d’un algorithme consiste à étudier le temps (complexité temporelle) ou la mémoire (complexité spatiale) nécessaires à l’exécution d’un algorithme. En fait, ce qui nous permettra de mesurer réellement l’efficacité d’un algorithme est l’évolution de la complexité spatiale ou temporelle en fonction de la taille des données.

6.2.2. Différents cas de complexité

La complexité peut dépendre de la taille des données mais elle peut également dépendre de la forme des données. On considère l’algorithme suivant qui recherche un élément à l’intérieur d’une liste.

In [1]: def recherche(elt, l):
   ...:     for x in l:
   ...:         if elt == x:
   ...:             return True
   ...:     return False
   ...:

On attribue à chaque test elt == x un coût élémentaire. Dans le meilleur des cas, l’élément recherché est le premier de la liste et la complexité vaut 1. Dans le pire des cas, l’élément recherché n’est pas présent dans la liste et la complexité est égale à la taille de la liste [2].

6.2.3. Complexité asymtotique

Pour décrire la complexité d’un algorithme, on utilise les notations de Landau et notamment le symbole \(\mathcal{O}\) [3]. Considérons par exemple la fonction suivante.

In [2]: def bidon(n):
   ...:     s = 0
   ...:     for i in range(n):
   ...:         for j in range(i):
   ...:             s += i**2 * j**2
   ...:     return s
   ...:

Si l’on considère les multiplications, les exponentiations et les sommes/affectations comme des opérations élémentaires, la complexité de cette fonction est

\[\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}4=2n(n-1)\]

On pourra dire que la complexité de cette fonction est en \(\mathcal{O}(n^2)\) [4].

On peut employer les adjectifs suivants pour qualifier certains types de complexité.

Complexité

Adjectif

\(\mathcal{O}(1)\)

constante

\(\mathcal{O}(\log n)\)

logarithmique

\(\mathcal{O}(n)\)

linéaire

\(\mathcal{O}(n^2)\)

quadratique

\(\mathcal{O}(2^n)\)

exponentielle

On emploiera également le symbole \(\Theta\). Si \((u_n)\) et \((v_n)\) sont deux suites, on dit que \(u_n=\Theta(v_n)\) si \(u_n=\mathcal{O}(v_n)\) et \(v_n=\mathcal{O}(u_n)\).