Comparaisons asymptotiques

Les comparaisons asymptotiques servent à comparer l'allure de deux fonctions à l'infini : plus grande, plus petite ou équivalente. En gros on oublie les constantes multiplicatives et additives qui dépendent du langage de programmation ou sont sujettes à interprétation.

C'est le grand informaticien D. Knuth qui a popularisé l'usage de ces fonctions dans le calcul de la complexité avec son célèbre article BIG OMICRON AND BIG OMEGA AND BIG THETA

Comme on utilise les fonctions asymptotique dans le cadre de la complexité on se restreindra aux fonctions issues de la complexité. En particulier :

On considérera dans la suite de ce cours uniquement des fonctions plus grande que 1 à partir d'un certain rang.

On utilise en algorithmie 3 fonctions asymptotiques différentes , la plus utilisée étant la fonction $\mathcal{O}()$ :

Définition
  • Une fonction $f(n)$ est en $\mathcal{O}(g(n))$ s'il existe 2 constantes $C_0$ et $N_0$ telles que $f(n) \leq C_0 \cdot g(n)$ pour tout $n > N_0$,
  • une fonction $f(n)$ est en $\Omega(g(N))$ s'il existe 2 constantes $C_0$ et $N_0$ telles que $f(n) \geq C_0 \cdot g(n)$ pour tout $n > N_0$,
  • une fonction $f(n)$ est en $\Theta(g(N))$ si $f(n)$ est en $\mathcal{O}(g(N))$ et $f(n)$ est en $\Omega(g(N))$.

Abus de notation

Par abus de langage on associera $\mathcal{O}(f(N))$ à une fonction en $\mathcal{O}(f(N))$ ce qui nous permettra d'écrire $f(N) = \mathcal{O}(g(N))$ plutôt que : "la fonction $f(N)$ est en $\mathcal{O}(g(N))$"

Ces trois fonctions partagent nombre de propriétés, ce qui les rend facile à manipuler. Par exemple la transitivité :

Proposition

  • Si $f(n) = \mathcal{O}(g(n))$ et $g(n) = \mathcal{O}(h(n))$ alors $f(n) = \mathcal{O}(h(n))$,
  • si $f(n) = \Omega(g(n))$ et $g(n) = \Omega(h(n))$ alors $f(n) = \Omega(h(n))$,
  • si $f(n) = \Theta(g(n))$ et $g(n) = \Theta(h(n))$ alors $f(n) = \Theta(h(n))$.

preuve

On ne va faire la preuve que pour les $\mathcal{O}$, la preuve étant identique pour les $\Omega$.

  • Si $f(n)$ est en $\mathcal{O}(g(n))$ il existe $C_0$ et $N_0$ tels que pour tout $n\geq N_0$ on ait $f(n) \leq C_0 g(n)$
  • Si $g(n)$ est en $\mathcal{O}(h(n))$ il existe $C'_0$ et $N'_0$ tels que pour tout $n\geq N'_0$ on ait $g(n) \leq C'_0 h(n)$

Donc pour tout $n \geq \max(N_0, N'_0)$ on a $f(n) \leq C_0 \cot C'_0 h(n)$ : $f(N)$ est en $\mathcal{O}(h(n))$

Deux exercices pour voir si on a compris comment ces fonctions se manipulent :

Montrez que :

  • si $f(n) = \mathcal{O}(g(n))$ alors une fonction en $\mathcal{O}(f(n) + g(n) + h(n))$ est également en $\mathcal{O}(g(n) + h(n))$,
  • si $g(n) = \Omega(f(n))$ alors une fonction en $\mathcal{O}(f(n) + g(n) + h(n))$ est également en $\mathcal{O}(g(n) + h(n))$,

corrigé

Si $f(n) = \mathcal{O}(g(n))$ il existe $C_0$ et $N_0$ tels que $f(n) \leq C_0 \cdot g(n)$ pour $n > N_0$ et si $f'(n) = \mathcal{O}(f(n) + g(n) + h(n))$ il existe $C'_0$ et $N'_0$ tels que $f'(n) \leq C'_0(f(n) + g(n) + h(n))$ pour $N > N'_0$.

De là, $f'(n) \leq C'_0 \cdot C_0 g(n) + C'_0 g(n) + C'_0 h(n)$ pour $n > \max( N_0, N'_0)$ ce qui implique $f'(n) \leq C'_0 \cdot (V_0 + 1) g(n) + C'_0h(n) \leq C'_0 \cdot (C_0 + 1) (g(n) + h(n))$ pour $n > \max(N_0, N'_0)$ : $f'(n) = \mathcal{O}(g(n) + h(n))$

La seconde implication se résout de façon similaire.

Montrez que si $f(n) = \mathcal{O}(g(n))$ alors une fonction en $\mathcal{O}(f(n) \cdot g(n) \cdot h(n) + h'(n))$ est également en $\mathcal{O}((g(N))^2 \cdot h(N)+ h'(N))$.

corrigé

Soit $f(n) = \mathcal{O}(g(n))$. Il existe donc $C_0$ et $N_0$ tels que $f(n) \leq C_0 \cdot g(n)$ pour $n > N_0$. Les fonctions étant positives à partir d'un certain rang, on peut considérer sans perte de généralité que $C_0 > 1$

Si $f'(n) = \mathcal{O}(f(n)\cdot g(n) \cdot h(n) + h'(n))$ il existe $C'_0$ et $N'_0$ tels que $f'(n) \leq C'_0(f(n) \cdot g(n) \cdot h(n) + h'(n))$ pour $n > N_0$.

De là, $f'(n) \leq C'_0 (C_0 g(n) \cdot g(n) \cdot h(n) + h'(n))$ pour $n > \max(N_0, N'_0)$ ce qui implique $f'(n) \leq C'_0C_0 g^2(n) \cdot h(n) + C'_0 h'(n) \leq C'_0C_0 g^2(n) \cdot h(n) + C'_0\cdot C_0\cdot h'(n) \leq C'_0C_0 \cdot (g(n)^2 \cdot h(n) + h'(n))$ pour $n > \max( N_0, N'_0)$.

On a bien : $f'(n) = \mathcal{O}((g(n))^2 \cdot h(n) + h'(n))$

Les trois fonctions vont avoir des utilités différentes lors du calcul de complexité.

Les $\mathcal{O}()$ pour majorer

Le but du calcul de complexité est d'être le plus proche possible du compte exact sans que ce soit pénible. Il existe plusieurs comparateur asymptotique, celui qui est le plus utilisé en algorithmie est le $\mathcal{O}$ :

Nombres constants d'opérations

Proposition

Pour tous réels strictement positifs $\alpha$ et $\beta$ :

$$ \begin{cases} \alpha = \mathcal{O}(1)\\ \alpha \cdot \mathcal{O}(\beta) = \mathcal{O}(1)\\ \end{cases} $$

preuve

  • Comme $\alpha = \alpha\cdot 1$ on a $\alpha = \mathcal{O}(1)$.
  • Si $f(n) = \mathcal{O}(\beta)$ il existe $C_0$ et $N_0$ tels que pour tout $n > N_0$ on ait $\alpha \cdot f(n) \leq \alpha \cdot C_0 \cdot \beta$, donc $f(n) \leq (\alpha \cdot C_0 \cdot \beta) \cdot 1$ : $\alpha \cdot f(n) = \mathcal{O}(1)$.

Ceci est pratique, car cela permet de ne pas compter toutes les opérations basiques précisément. Ainsi, en reprenant l'exemple initial de calcul de complexité :

ref age int
age ← 16
si ((age ≥ 12) et (age < 18)):
    personne ← "adolescent"

Un nombre total d'instructions de $3 \cdot \mathcal{O}(1) = \mathcal{O}(1)$ instructions.

Nombre linéaire d'opérations

Le plus grand intérêt de l'utilisation de la fonction asymptotique $\mathcal{O}$ est que l'on peut facilement négliger les constantes additives et multiplicatives pour se concentrer sur l'allure générale.

Proposition

Pour tous réels strictement positifs $\alpha$ et $\beta$ :

$$ \mathcal{O}(\alpha \cdot g(n) + \beta) = \mathcal{O}(g(n)) $$

preuve

Par hypothèse il existe $N_1$ tel que $g(n) \geq 1$ pour $n \geq N_1$.

  • Si $f(n) = \mathcal{O}(\alpha \cdot g(n) + \beta)$ il existe $C_0$ et $N_0$ tels que pour tout $n\geq N_0$ on ait $f(n) \leq C_0 \cdot (\alpha \cdot g(n) + \beta) = C_0 \cdot \alpha \cdot g(n) + C_0 \cdot \beta$, donc $f(n) \leq (C_0 \cdot \alpha + C_0 \cdot \beta) \cdot g(n)$ pour $n \geq \max(N_0, N_1)$ : $f(n) = \mathcal{O}(g(n))$.
  • Réciproquement, si $f(n) = \mathcal{O}(g(n))$ il existe $C_0$ et $N_0$ tels que pour tout $n\geq N_0$ on ait $f(n) \leq C_0\cdot g(n)$, donc $f(n) \leq \max(1, \frac{1}{\min(\alpha, \beta)}) \cdot C_0 (\alpha g(n) + \beta)$ pour $n \geq \max(N_0, N_1)$ : $f(n) = \mathcal{O}(\alpha \cdot g(n) + \beta)$.

Proposition

Pour tous réels strictement positifs $\alpha$ et $\beta$ :

  • $\alpha \cdot \mathcal{O}(f(n)) + \beta \cdot \mathcal{O}(g(n)) = \mathcal{O}(f(n) + g(n))$
  • $\mathcal{O}(f(n)) \cdot \mathcal{O}(g(n)) = \mathcal{O}(f(n) \cdot g(n))$

preuve

Si $f'(n) = \mathcal{O}(f(n))$ et $g'(n) = \mathcal{O}(g(n))$, il est clair que $\alpha \cdot f'(n) = \mathcal{O}(\alpha \cdot f(n))$ et $\beta \cdot g'(n) = \mathcal{O}(\beta \cdot g(n))$ donc $\alpha \cdot f'(n) = \mathcal{O}(f(n))$ et $\beta \cdot g'(n) = \mathcal{O}(g(n))$ en utilisant la proposition précédente.

Si $1 \leq \alpha \cdot f'(n) \leq C_0 \cdot f(n)$ pour $n \geq N_0$ et $1\leq \beta \cdot g'(n) \leq C'_0 \cdot g(n)$ pour $n \geq N'_0$ on a :

  • $\alpha \cdot f'(n) + \beta \cdot g'(n) \leq \max(C_0, C'_0) \cdot (f(n) + g(n))$ pour $n \geq \max(N_0, N'_0)$
  • $f'(n) \cdot g'(n) \leq C_0 \cdot C'_0 \cdot (f(n) \cdot g(n))$ pour $n \geq \max(N_0, N'_0)$

La proposition précédente permet de résoudre les problèmes de comptages. Les pseudo-code suivant ayant même complexité, $\mathcal{O}(n)$ :

pour chaque i de [2 .. n]:
    affiche i

et

ref i ← 2
tant que i ≤ n:
  affiche i
  i ← i + 1

Tout devient plus simple !

À retenir
  • si le nombre d'itération est $n$ plus ou moins une constante, il est en $\mathcal{O}(n)$,
  • si la condition de répétition d'une boucle tant que est en $\mathcal{O}(1)$, seul, le no,bre d'itération va compter dans le calcul de la complexité.

On ne peut cependant appliquer la règle que pour des constantes ! Si $f(n) = \mathcal{O}(g(n))$ on a $n \cdot f(n) = \mathcal{O}(n\cdot g(n))$ puisque $n$ est une fonction en $\mathcal{O}(n)$ pas du tout en $\mathcal{O}(1)$.

On ne peut pas simplifier les éléments variables

Si le nombre d'opérations élémentaires est variable on a : $n \cdot \mathcal{O}(1) = \mathcal{O}(n)$.

Calcul de complexité max

Enfin, pour le calcul de complexité maximale le $\mathcal{O}$ se trouver être très adapté. Prenons par exemple notre algorithme recherche :

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

Toutes les instructions de l'algorithme sont en $\mathcal{O}(1)$ :

Sa complexité $C(T, x)$ d'une exécution vaut alors :

$$ \begin{array}{lclr} C(T, x) &=& \mathcal{O}(1) + & \text{ligne 1}\\ && k \cdot ( & \text{nombre d'exécution de boucle}\\ && \mathcal{O}(1) + & \text{affectation de la ligne 2}\\ && \mathcal{O}(1)) + & \text{test de la ligne 3}\\ && \mathcal{O}(1) + & \text{retour de la ligne 3 ou 4}\\ \end{array} $$

Pour ce calcul on a compté :

La complexité totale de l'algorithme est donc égale au nombre $k$ de fois où ou la boucle tant que est exécutée. Comme elle est exécutée au maximum $n$ fois où $n$ est la longueur du tableau on en conclut que :

Les $\Omega()$ pour minorer

De façon symétrique, les grand Omega, $\Omega()$, permettent de caractériser les fonctions qui en minorent une autre. Elle est le symétrique de la fonction $\mathcal{O}$ :

Proposition

$f(N) = \mathcal{O}(g(N)) \Leftrightarrow g(N) = \Omega(f(N))$

preuve

Si $f(N) = \mathcal{O}(g(N))$, il existe $c_0$ et $N_0$ tels que $f(N) \leq c_0 \cdot g(N)$ pour $N > N_0$. Les fonctions étant positives, on a $c_0 > 0$ et donc $\frac{1}{c_0} \cdot f(N) \leq g(N)$ pour $N > N_0$ : $g(N) = \Omega(f(N))$

Réciproquement, si $g(N) = \Omega(f(N))$, il existe $c_0$ et $N_0$ tels que $c_0 \cdot f(N) \leq g(N)$ pour $N > N_0$. Les fonctions étant positives, on a $c_0 > 0$ et donc $\frac{1}{c_0} \cdot g(N) \geq f(N)$ pour $N > N_0$ : $f(N) = \mathcal{O}(g(N))$

Les propositions précédentes démontrées pour les $\mathcal{O}$ fonctionnent également pour les $\Omega$ (on change le signe de l'inégalité dans la démonstration).

linéarité de la comparaison

Proposition

Pour tous réels strictement positifs $\alpha$ et $\beta$ :

$$ \begin{cases} \alpha = \Omega(1)\\ \alpha \cdot \Omega(\beta) = \Omega(1)\\ \Omega(\alpha \cdot g(n) + \beta) = \Omega(g(n))\\ \alpha \cdot \Omega(f(n)) + \beta \cdot \Omega(g(n)) = \Omega(f(n) + g(n))\\ \Omega(f(n)) \cdot \Omega(g(n)) = \Omega(f(n) \cdot g(n)) \end{cases} $$

Calcul de complexité min

Les $\Omega$ sont utilisés pour minorer des complexité et donc très utiles pour des calculs de complexité min. En reprenant l'algorithme recherche, l'algorithme va forcément rentrer au moins une fois dans la boucle tant que, on en conclut donc que :

$$ C(n) = \Omega(1) $$

Cela ne veut pas (encore) dire qu'il existe des tableaux et des entiers pour lesquels l'exécution de l'algorithme ne va pas dépendre de la longueur du tableau, juste qu'il prendra au moins un temps constant quelque soient les entrées (ce qui n'es pas très informatif pour cet algorithme, je vous l'accorde).

Les $\Theta()$ pour les équivalences

Enfin, la dernière comparaison asymptotique utilisée en algorithme est le grand theta. Elle rend compte de fonctions aux allures similaires :

Proposition

$f(n) = \Theta(g(n)) \Rightarrow g(n) = \Theta(f(n))$

preuve

si $f(n)$ est en $\Theta(g(n))$, alors :

  • $f(n) = \Theta(g(n))$ donc $g(n)$ est en $\Omega(f(n))$
  • $f(n) = \mathcal{O}(g(n))$ donc $g(n)$ est en $\mathcal{O}(f(n))$

Elle respecte bien sûr également les propriétés communes aux $\mathcal{O}$ et $\Omega$ :

Proposition

Pour tous réels strictement positifs $\alpha$ et $\beta$ :

$$ \begin{cases} \alpha = \Theta(1)\\ \alpha \cdot \Theta(\beta) = \Theta(1)\\ \Theta(\alpha \cdot g(n) + \beta) = \Theta(g(n))\\ \alpha \cdot \Theta(f(n)) + \beta \cdot \Theta(g(n)) = \Theta(f(n) + g(n))\\ \Theta(f(n)) \cdot \Theta(g(n)) = \Theta(f(n) \cdot g(n)) \end{cases} $$

Enfin, la proposition suivante (triviale) lies les 3 fonctions :

Proposition

$$ \begin{cases} f(n) = \Theta(g(n)) \Leftrightarrow f(n) = \Omega(g(n)) \text{ et } g(n) = \Omega(f(n))\\ f(n) = \Theta(g(n)) \Leftrightarrow f(n) = \mathcal{O}(g(n)) \text{ et } g(n) = \mathcal{O}(f(n))\\ \end{cases} $$

Les $\Theta$ sont utilisés pour calculer la meilleure estimation possible (à un facteur multiplicatif et additif prêt) d'une complexité.

Ainsi, pour l'algorithme recherche, on sait que si $n$ est la longueur du tableau en entrée :

Ceci est important car on pourrait très bien dire que la complexité de l'algorithme recherche est en $\mathcal{O}(n^2)$, voir en $\mathcal{O}(n!)$ qui est tout aussi exact.

À retenir

Lorsque c'est possible, essayez de trouver des complexités maximale et minimales en $\Theta$ pour vos algorithmes.

Pour cela on commence par trouver un encadrement en $\mathcal{O}$ et en $\Omega$ puis on trouve des instance de l'algorithme pour lesquels ces bornes sont atteintes.