Calcul de complexité

Analyser un algorithme revient à prévoir les ressources (i.e. la quantité de mémoire) nécessaires à cet algorithme et à mesurer son temps d'exécution. En général, quand on analyse plusieurs algorithmes candidats pour un problème donné, on arrive aisément à identifier le candidat le plus efficace. Ce type d'analyse peut révéler plusieurs candidats valables et permet d'éliminer les autres.

L'analyse d'un algorithme, même simple, peut s'avérer difficile. Il est donc nécessaire de se donner des outils mathématiques pour parvenir à nos fins.

Notation asymptotique

Les fonctions que l'on considère dans cette section sont des fonctions de $\mathbb{N}$ dans $\mathbb{N}$. Soient $f$ et $g$ deux fonctions.

Définition 1   On dira que $f=\ensuremath{\mathcal{O}}\xspace (g)$ si et seulement si il existe $c>0$ et $n_0\in\ensuremath{\mathbb{N}}\xspace$ tel que

$$\forall n\geqslant n_0: f(n)\leqslant c\cdot g(n)$$

Définition 2   On dira que $f=\Omega(g)$ si et seulement si il existe $c>0$ et $n_0\in\ensuremath{\mathbb{N}}\xspace$ tel que

$$\forall n\geqslant n_0: f(n)\geqslant c\cdot g(n)$$

Définition 3   On dira que $f=o(g)$ si et seulement si $$\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = 0$$.

Définition 4   On dira que $f=\Theta(g)$ si et seulement si $f=\ensuremath{\mathcal{O}}\xspace (g)$ et $g=\ensuremath{\mathcal{O}}\xspace (f)$. On remarquera que $f=\Theta(g)$ si et seulement si $g=\Theta(f)$.

Exercice 18   Parmis les affirmation suivantes, lesquelles sont vraies ?

$f(n)$	$g(n)$	$f=\ensuremath{\mathcal{O}}\xspace (g)$	$g=\ensuremath{\mathcal{O}}\xspace (f)$	$f=o(g)$	$g = o(f)$	$f=\Theta(g)$
$n+1$	$n^4+3n -2$	...	...	...	...	...
$n+4$	$4n$	...	...	...	...	...
$\frac{1}{10}n^3 + 100n^2 +10000$	$n^3$	...	...	...	...	...
$2^{n+1}$	$2^n$	...	...	...	...	...
$2^{2n}$	$2^n$	...	...	...	...	...
$(n+a)^b$	$n^b$	...	...	...	...	...
$n^n$	$n!$	...	...	...	...	...
$2^n$	$n!$	...	...	...	...	...
$n$ si $n\equiv0[2]$ et 1 sinon	$n$	...	...	...	...	...

Voir réponse 18.

Remarque 1   Comme on ne manipule que des fonctions de $\mathbb{N}$ dans $\mathbb{N}$ et que l'on s'intéresse uniquement à leur comportement à l'infini, on pourra sommer les $\mathcal{O}$ et les $\Theta$ sans risque.

L'utilisation de la notation $\mathcal{O}$ permet de majorer le comportement d'une fonction et la notation $\Theta$ permet d'éviter d'avoir une majoration trop grossière. La notation $\Omega$ signifie qu'une fonction croit au moins aussi vite qu'un autre.

Ces notations permettent donc de comparer deux fonctions. On pourra faire l'analogie suivante avec la comparaison sur des nombres réels:

$$\begin{array}{ccc} f(n) = \ensuremath{\mathcal{O}}\xspace (g(... ...ox & a = b\\ f(n) = o(g(n)) & \approx & a \ll b\\ \end{array}$$

Complexité d'un algorithme

Le temps d'exécution d'un algorithme sur une entrée particulière est le nombre d'opération élémentaires exécutées. Reprenons un à un les algorithmes de la section 3.1 et évaluons leur complexité

Sommation

Pour le moment, nous dirons que chaque ligne de notre pseudo-code demande une quantité de temps constante. L'execution de la ligne $i$ prendra donc un temps $c_i$. Dans l'étude qui va suivre, le temps d'exécution va évoluer d'une formulation brouillonne utilisant tous les coûts des $c_i$, vers une formulation beaucoup plus simple, plus concise et plus facile à manipuler.

Le coût de l'exécution de l'algorithme dépend donc de n. On a donc

$$\begin{split}C(n) & = c_4 + c_5 n + c_6 \sum_{j=1}^n j + c_7 ... ..._7}{2}+c_5\right)n + (c_4 + c_8)\\ & = \Theta(n^2) \end{split}$$

Fibonacci

Itératif simple

Le temps d'exécution de cet algorithme est donc $\Theta(n)$. On remarquera que l'on utilise un tableau de taille $n$ et une variable de boucle. L'occupation mémoire est donc $\Theta(n)$.

Itératif rusé

Le temps d'exécution de cet algorithme est donc encore $\Theta(n)$. Par contre, on n'utilise qu'un tableau de taille 3 et une variable de boucle. L'occupation mémoire est donc $\Theta(1)$, ce qui est bien meilleur.

Récursif

On a donc

$$\begin{split}C(n) &= c_4+c_5+c_6+c_7 + C(n-1) + C(n-2) \\ &= \alpha + C(n-1) + C(n-2) \end{split}$$

Il est parfaitement possible d'obtenir une forme close pour $C(n)$ mais nous nous contenterons pour l'instant d'un encadrement.

$$\begin{split}C(n) &= \alpha + C(n-1) + C(n-2) \\ &\geqslant ... ...^{n/2} 2^i\right) = \alpha \left(2^{n/2+1}-1\right) \end{split}$$

Donc $C(n)=\Omega(2^{n/2})$. De même, on a

$$\begin{split}C(n) &= \alpha + C(n-1) + C(n-2) \\ &\leqslant ... ...i=0}^{n} 2^i\right) = \alpha \left(2^{n+1}-1\right) \end{split}$$

On a donc $C(n)=\ensuremath{\mathcal{O}}\xspace (2^{n})$

L'évaluation de l'occupation mémoire est un peu différente. Un arbre d'appel permet de se convaincre aisément qu'il est en $\Theta(n)$. Le temps d'exécution de l'algorithme est de l'ordre du nombre de noeuds de l'arbre d'appel alors que l'occupation mémoire est de l'ordre de la hauteur de l'arbre.