Home
About

Comparaisons asymptotiques

Cours/Algorithmie/Mesures de complexités/Comparaisons asymptotiques

Les comparaisons asymptotiques servent à comparer l'allure de deux fonctions à l'infini : plus grande, plus petite ou équivalente.

On considérera dans la suite de ce cours uniquement des fonctions positives, ce qui est le cas lorsque l'on appliquera à la mesure de complexité. Donc :

Certaines équivalences ci-dessous ne sont vraies que dans le cas de fonctions positives.

Fonctions asymptotiques

On montre 3 fonctions asymptotiques, a plus utilisée étant la fonction $\mathcal{O}()$

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

Les grand O, $\mathcal{O}()$, permettent de caractériser les fonctions qui en majorent une autre.

Une fonction $f(N)$ est en $\mathcal{O}(f'(N))$ s'il existe 2 constantes $c_0$ et $N_0$ tels que $f(N) \leq c_0 \cdot f'(N)$ pour tout $N > N_0$.

Connaître le comportement en $\mathcal{O}$ de $f(N)$ nous donne un majorant de son allure lorsque $N$ devient grand.

Par abus de langage, on notera :

Les $\Omega()$ pour minorer

De façon symétrique, on défini les grand Omega, $\Omega()$, qui permettent de caractériser les fonctions qui en minorent une autre.

Une fonction $f(N)$ est en $\Omega(f'(N))$ s'il existe 2 constantes $c_0$ et $N_0$ tels que $f(N) \geq c_0 \cdot f'(N)$ pour tout $N > N_0$.

La fonction $\Omega$ est le symétrique de la fonction $\mathcal{O}$ :

$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 $\Theta()$ pour les équivalences

Une fonction $f(N)$ est en $\Theta(f'(N))$ si :

  • $f(N)$ est en $\mathcal{O}(f'(N))$
  • $f(N)$ est en $\Omega(f'(N))$

La fonction $\Omega$ rend compte de fonctions aux allures similaires :

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

preuve

Clair grace à la propriété précédente qui montre que si $f(N)$ est en $\Theta(f'(N))$, alors on a également :

  • $f'(N)$ est en $\Omega(f(N))$
  • $f'(N)$ est en $\mathcal{O}(f(N))$

et donc $f'(N)$ est en $\Theta(f(N))$

Règles de transitions entre fonctions asymptotiques

Liens entre fonctions asymptotiques

Commençons par deux règles liant les 3 fonctions :

$f(N) = \Theta(g(N)) \Leftrightarrow f(N) = \Omega(g(N)) \text{ et } g(N) = \Omega(f(N))$

preuve

Immédiat grace à la définition de $\Theta()$ et à la propriété liant $\Omega$ et $\mathcal{O}$.

$f(N) = \Theta(g(N)) \Leftrightarrow f(N) = \mathcal{O}(g(N)) \text{ et } g(N) = \mathcal{O}(f(N))$

preuve

Immédiat grace à la définition de $\Theta()$ et à la propriété liant $\Omega$ et $\mathcal{O}$.

Cas des constantes

La règle suivante va se retrouver fort utile :

Règle des constantes additives

$ A = \Theta(1)$, avec $A$ une constante strictement positive.

preuve

Soit $f(N) = \mathcal{O}(A)$. Il existe donc $c_0$ et $N_0$ tels que pour tout $N > N_0$, on ait $f(N) \leq c_0 \cdot A$.

En posant $c'_0 = c_0 \cdot A$, on a $f(N) \leq c'_0 \cdot 1$ pour tout $N > N_0$. Donc : $f(N) = \mathcal{O}(1)$.

Réciproquement, soit $f(N) = \mathcal{O}(1)$.

Il existe donc $c_0$ et $N_0$ tels que pour tout $N > N_0$, on ait $f(N) \leq c_0 \cdot 1$. En posant $c'_0 = c_0 / A$, on a $f(N) \leq c'_0 \cdot A$ pour tout $N > N_0$. Donc $f(N) = \mathcal{O}(A)$.

Règle des constantes multiplicatives

$ A\cdot f(N) = \Theta(f(N))$, avec $A$ une constante strictement positive.

preuve

Pour tout $N > 0$, on a $A\cdot f(N) \leq c_0\cdot f(N)$ avec $c_0 = A$ ce qui prouve que A\cdot f(N) = \mathcal{O}(f(N))$.

De même, pour tout $N>0$, $A\cdot f(N) \geq c_0\cdot f(N)$ avec $c_0 = A$ ce qui prouve que A\cdot f(N) = \Omega(f(N))$.

Arithmétique des fonctions asymptotiques

Enfin, les règles suivantes (si les fonctions sont positives) permettent de combiner les fonctions asymptotiquement comparables. Elles sont explicitées avec les $\mathcal{O}()$ mais fonctionnent également avec les $\Omega()$ et les $\Theta$ :

Règle des sommes

En combinant les $\mathcal{O}$ pour $f$ et $g$, deux fonctions positives :

$\mathcal{O}(f(N)) + \mathcal{O}(g(N)) \Rightarrow \mathcal{O}(f(N) + g(N))$

preuve

Soient $f'(N) = \mathcal{O}(f(N))$ et $g' = \mathcal{O}(g(N))$, il existe donc $c_0$, $c'_0$, $N_0$ et $N'_0$ tels que $f'(N) \leq c_0 f(N)$ pour $N > N_0$ et $g'(N) \leq c'_0 g(N)$ pour $N > N'_0$.

On a alors $f'(N) + g'(N) \leq c_0 f(N) + c'_0 g(N) \leq \max(c_0, c'_0) \cdot (f(N) + g(N))$ pour $N > \max( N_0, N'_0)$.

On a bien : $f'(N) + g'(N) = \mathcal{O}(f(N) + g(N))$.

Règle des produits

En combinant les $\mathcal{O}$ pour $f$ et $g$ deux fonctions positives :

$\mathcal{O}(f(N)) \cdot \mathcal{O}(g(N)) \Rightarrow \mathcal{O}(f(N) \cdot g(N))$

preuve

Soient $f'(N) = \mathcal{O}(f(N))$ et $g' = \mathcal{O}(g(N))$, il existe donc $c_0$, $c'_0$, $N_0$ et $N'_0$ tels que $f'(N) \leq c_0 f(N)$ pour $N > N_0$ et $g'(N) \leq c'_0 g(N)$ pour $N > N'_0$.

On a alors $f'(N) \cdot g'(N) \leq c_0f(N) \cdot c'_0g(N) = c_0c'_0 \cdot (f(N)g(N)) $ pour $N > \max(N_0, N'_0)$.

Les trois règles suivantes permettent de négliger les fonctions majorées. Elles fonctionnent dans l'autre sens pour les $\Omega$ et ne fonctionnent pas pour les $\Theta$ :

Règle des polynômes

$\mathcal{O}(N^p) \Rightarrow \mathcal{O}(N^q)$ pour $q \geq p$

preuve

Soit $f(N) = \mathcal{O}(N^p)$. Il existe donc $c_0$ et $N_0$ tels que $f(N) \leq c_0 \cdot N^p$ pour $N > N_0$.

Comme $1 < 2 \cdot N^\alpha$ pour $\alpha \geq 0$ et $N> 1$, on a $N^p \leq N^p \cdot (2 \cdot N^{q-p}) = c_0 \cdot N^q$ pour $c_0 = 2$, $N > 1 = N_0$ et $p \leq q$. Donc $N^p = \mathcal{O}(N^q)$ pour tout $p \leq q$

Règle des sommes négligeables

$f(N) = \mathcal{O}(g(N))$ implique $\mathcal{O}(f(N) + g(N) + h(N)) \Rightarrow \mathcal{O}(g(N) + h(N))$ pour f, g et h des fonctions positives.

preuve

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$.

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 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 (c_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)$

On a bien : $f'(N) = \mathcal{O}(g(N) + h(N))$

Règle des produits négligeables

$f(N) = \mathcal{O}(g(N))$ implique $\mathcal{O}(f(N) \cdot g(N) \cdot h(N) + h'(N)) \Rightarrow \mathcal{O}((g(N))^2 \cdot h(N)+ h'(N))$ pour f, g, h et h' des fonctions positives.

preuve

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, on pet 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 c_0h'(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))$

Usages

Les fonctions asymptotiques permettent d'utiliser :