Comparaison asymptotique

En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier le comportement d'une fonction au voisinage d'un point (ou en l'infini), en regard du comportement d'une autre fonction, souvent choisie sur une échelle de référence. Cette échelle est généralement une échelle de monômes. Cette méthode peut être utilisée pour traiter de gros volumes de données ou pour étudier le comportement de systèmes complexes en physique et en informatique, en particulier en théorie de la complexité des algorithmes.

Cet article présente quelques cas de comparaison asymptotique, et introduit les notations de Landau et de Hardy.

Exemples de comparaison

La relation de prépondérance

Article détaillé : Fonction négligeable.

Exemple

Soit $f$ et $g$ les fonctions réelles définies par les formules $f(x)=\cos(x)+2$ et $g(x)=x$.

Par une étude triviale des deux fonctions, on sait que $g$ prend des valeurs aussi grandes que l'on veut au voisinage de l'infini, tandis que $f$ ne peut prendre des valeurs qu'entre 1 et 3. L'écart entre $f$ et $g$ au voisinage de l'infini ne cesse d'augmenter et n'est pas borné. Dans ce contexte, on peut dire que $f$ est négligeable devant $g$, ou que g est prépondérante devant f, au voisinage de l'infini, on écrit (notation de Landau):

$f(x) = o(g(x)) \ (x\rightarrow\infty)$

ou (notation de Hardy, désuète)

$f (x) \prec g(x)\ (x\rightarrow\infty)$ .

Définition formelle lorsque la fonction g ne s'annule pas

Pour décrire formellement cette « distance » entre deux fonctions, on va utiliser le comportement du quotient $\frac f g$.

Soit $a \in \mathbb{R} \cup \left\{ +\infty ; -\infty \right\}$.

Soient $f$ et $g$ deux fonctions de la variable réelle $x$. On suppose que $g$ ne s'annule pas sur un voisinage de a. On dit que $f$ est négligeable devant $g$, ou que $g$ est prépondérante devant $f$ en $a$, et on note $f(x) = \underset{ \overset { x \rightarrow a } {} } {o} (g(x))$, lorsque

$\frac {f(x)} {g(x)} \underset{ \overset { x \rightarrow a } {} } {\longrightarrow} 0$.

Si le contexte est clair, on ne précise pas le domaine d'étude et on note : $f(x) = o (g(x))$, voire $f = o(g)$. Cependant, la notation est toujours associée à un lieu a et au voisinage de ce lieu : être négligeable est un concept local.

La notation de Landau associée à négligeable est $f(x) = o(g(x))$ (qu'on note aussi $f(x) \in o(g(x))$) et s'appelle petit o, tandis que la notation de Hardy se note $f \prec g$. On utilise aujourd'hui exclusivement la notation de Landau.

Propriétés

Par abus de langage, on effectue des « opérations » sur les « petits o », c'est-à-dire sur les négligeables. En effet, on peut dire que :

• $o(f) + o(f) = o(f)$
• $o(f) - o(f) = o(f)$

Exemples

• $x^2 + 2012 = \underset{ \overset { x \rightarrow \infty } {} } {o} (x^3)$
• Pour toute fonction $\varepsilon$, telle que $\varepsilon (x) \underset{ \overset { x \rightarrow a } {} } {\longrightarrow} 0$, on a : $\varepsilon (x) = \underset{ \overset { x \rightarrow a } {} } {o} (1)$

Équivalence

Article détaillé : Équivalent.

Définition formelle

Soit $a \in \mathbb{R} \cup \left\{ +\infty ; -\infty \right\}$.

Soient $f$ et $g$ deux fonctions de la variable réelle $x$. On suppose que $g$ ne s'annule pas sur un voisinage de a. On dit que $f$ est équivalent à $g$ en $a$, ou que $g$ équivaut à $f$ en $a$, et on note

$f(x) \underset{ \overset { x \rightarrow a } {} } {\sim} g(x)$, lorsque $f(x) - g(x) = \underset{ \overset { x \rightarrow a } {} } {o} (g(x))$.

Exemple

$\cos x + x^{20} + \exp(x) \underset{ \overset { x \rightarrow \infty } {} } {\sim} \exp(x)$

Domination

La notation grand O de Landau dénote le caractère dominé d'une fonction par rapport à une autre.

Généralement on utilise la lettre O majuscule, quoiqu'en principe il s'agit de la lettre grecque omicron majuscule, rarement dessinée de manière clairement différente du O. Surtout ne pas employer le chiffre zéro.

Définition formelle

Soient f et g deux fonctions de la variable réelle x. On dit que f est dominée par g en +∞, ou que g domine f en +∞, et on note (notation de Landau)

$f(x)=O(g(x)) \ (x\rightarrow\infty),$

ou (notation de Vinogradov)

$f(x)\ll g(x)) \ (x\rightarrow\infty),$

lorsqu'il existe des constantes N et C telles que

$\forall x>N\qquad \left|f(x)\right| \le C \left|g(x)\right|.$

Intuitivement, cela signifie que f ne croît pas plus vite que g.

De même, si a est un nombre réel, nous écrivons

$f(x)=\underset{x\to a}O(g(x))$

s’il existe des constantes d > 0 et C telles que

$\forall x \qquad \left|x - a\right| < d \implies \left|f(x)\right| \le C \left|g(x)\right|.$

La première définition est la seule utilisée en informatique (où typiquement seules les fonctions positives à variable entière n sont considérées, les valeurs absolues pouvant être ignorées).

Exemples

• $4x^3 + 2012 x^2=\underset{x\to\infty}O(x^3).$
• En un point a, si f est négligeable devant g ou équivalente à g, alors elle est dominée par g.
• Une fonction f est bornée sur un voisinage de a si et seulement si $f(x)=\underset{x\to a}O(1)$.

Utilisation des comparaisons

Développements limités

En mathématiques, il est souvent important de garder un œil sur le terme d'erreur d'une approximation. Cette notation est particulièrement utilisée dès que l'on a affaire à des développements limités et à des calculs d'équivalents. Par exemple, le développement de la fonction exponentielle à l'ordre 2 peut aussi s'écrire:

$e^x = 1+x+\frac{1}{2} x^2+o(x^2) \ {\rm quand}\ x \rightarrow 0$

pour exprimer le fait que l'erreur, la différence $e^x - \left(1 + x +\frac{x^2}{2}\right)$, est négligeable devant $x^2$ quand $x$ tend vers 0.

Il faut préciser que le nombre d'opérandes dans ce genre d'écriture doit être constant (ne pas dépendre de la variable) : une "formule" telle que $o(n)+o(n)+\dots+o(n)=o(n)$ est fausse si les points de suspension cachent n termes.

Échelle de comparaison

Voici une liste de catégories de fonctions couramment utilisées en analyse. Les fonctions sont classées par ordre de croissance de la plus lente à la plus rapide, quand la variable (notée ici n) tend vers $+\infty$. c est une constante arbitraire.

notation		croissance
O(1)		bornée par une constante
O(log(n))		logarithmique
O((log(n))c)		polylogarithmique
O(n)		linéaire
O(n log(n))		parfois appelée « linéarithmique », ou « quasi-linéaire »
O(n2)		quadratique
O(nc)		polynomiale
O(cn)		exponentielle, parfois « géométrique »
O(n!)		factorielle

O(n^c) et O(cⁿ) sont très différents. Le dernier exprime une croissance bien plus rapide, et ce pour n'importe quelle constante c>1. Une fonction qui croît plus rapidement que n'importe quel polynôme est appelée super-polynomiale. Une fonction qui croît plus lentement que toute exponentielle est appelée sous-exponentielle. Il existe des fonctions à la fois super-polynômiales et sous-exponentielles comme, par exemple, la fonction n^log(n). Certains algorithmes ont un temps de calcul de ce type, comme celui de la factorisation d'un nombre entier.

Remarquons aussi que O(log n) est exactement identique à O(log(n^c)), puisque ces deux logarithmes sont multiples l'un de l'autre par un facteur constant et que la notation grand O « ignore » les constantes multiplicatives. De manière analogue, les logarithmes dans des bases constantes différentes sont équivalents.

La liste précédente est utile à cause de la propriété suivante : si une fonction f est une somme de fonctions, et si une des fonctions de la somme grimpe plus vite que les autres, alors celle qui croît le plus vite détermine l'ordre de croissance de f(n).

ex.: si f(n) = 10 log(n) + 5 (log(n))³ + 7 n + 3 n² + 6 n³, alors f(n) = O(n³).

Fonction à plusieurs variables

Cette notation peut aussi être utilisée avec des fonctions de plusieurs variables :

L'écriture :	$f(n,m) = n^2 + m^3 + O(n+m)\;$ quand $m,n\to +\infty$
correspond à la proposition :	$\exists C \quad \exists N \quad \forall n,m > N \qquad |f(n,m) -n^2-m^3 |\le C(n+m)$

Évidemment, cette notation abuse du symbole d'égalité, puisqu'elle viole l'axiome d'égalité : « des choses égales à la même chose sont égales entre elles » (autrement dit, avec cette notation, l'égalité n'est plus une relation d'équivalence). Pour être plus formellement correctes, certaines personnes préfèrent définir $O (g(x))$ comme un ensemble de fonctions, dont les éléments sont toutes les fonctions qui ne grandissent pas plus vite que $g$, et utilisent les notations ensemblistes pour indiquer si une fonction donnée est un élément de l'ensemble ainsi défini. Les deux conventions sont couramment utilisées mais la notation la moins soignée est jusqu'à présent la plus souvent rencontrée. Pour éviter ce problème on utilise (également couramment) la notation de Vinogradov (voir ci-dessous).

Un autre problème est qu'il faut clairement indiquer la variable par rapport à laquelle le comportement asymptotique est examiné. Une affirmation telle que $f(n,m) = O (m^n)\;$ n'a pas le même sens selon qu'elle est suivie de « quand $m,n\to +\infty$ » ou, par exemple, de « (pour tout $m$ fixé) quand $n\to +\infty$ ». Cette difficulté se produit rarement dans la pratique.

La famille de notations de Landau O, o, Ω, ω, Θ, ~

Notation	Nom	Intuition	Lorsque $n \to \infty$, à partir d'un certain rang...	Définition
$f(n) \in O(g(n))$	Grand O (omicron)	$f$ est bornée, par le dessus, par $g$ asymptotiquement (à un facteur près)	$|f(n)| \leq |g(n)|\cdot k$ pour un k > 0	$\exists k>0, \exists n_0 \; \forall n>n_0 \; |f(n)| \leq |g(n)|\cdot k$
$f(n) \in \Omega(g(n))$	Grand Omega	$f$ est minorée par $g$ asymptotiquement (à un facteur près) (En théorie des nombres : « $f(n)\not= o(g(n))$ », voir Notation de Landau.)	$|f(n)| \geq |g(n)|\cdot k$ pour un k > 0 ... (En théorie des nombres : ... pour une suite de nombres $n\rightarrow\infty$)	$\exists k>0, \exists n_0 \; \forall n>n_0 \; |g(n)|\cdot k \leq |f(n)|$ (En théorie des nombres : $\exists k>0, \forall n_0 \; \exists n>n_0 \; |g(n)|\cdot k \leq |f(n)|$)
$f(n) \in \Theta(g(n))$	Grand Theta	$f$ est dominée et soumise à $g$ asymptotiquement	$|g(n)|\cdot k_1 \leq |f(n)| \leq |g(n)|\cdot k_2$ pour un k1 > 0, et un k2 > 0	$\exists k_1,k_2>0, \exists n_0 \; \forall n>n_0$ $|g(n)|\cdot k_1 < |f(n)| < |g(n)|\cdot k_2$
$f(n) \in o(g(n))$	Petit o (omicron)	$f$ est dominée par $g$ asymptotiquement	$|f(n)| \le |g(n)|\cdot \varepsilon$, quel que soit $\varepsilon$ > 0 (fixé).	$\forall \varepsilon>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| \le |g(n)|\cdot \varepsilon$
$f(n) \in \omega(g(n))$	Petit Omega	$f$ domine $g$ asymptotiquement	$|f(n)| \ge |g(n)|\cdot k$ pour tout k > 0	$\forall k>0 \; \exists n_0 \; \forall n>n_0 \; |g(n)|\cdot k \le |f(n)|$
$f(n)\sim g(n)\!$	de l'ordre de ; équivalent à	$f$ est égale à $g$ asymptotiquement	$|f(n)-g(n)|<\varepsilon |g(n)|$, quel que soit $\varepsilon$ > 0 (fixé).	$\forall \varepsilon>0\;\exists n_0\;\forall n>n_0\;|f(n)-g(n)|<\varepsilon |g(n)|$

La notation de Landau a été conçue de manière à être sa propre mnémotechnique, comme on peut le lire dans la colonne Lorsque $n \to \infty$, à partir d'un certain rang.... En effet omicron peut être lu «o-micro-n» et omega «o-mega». Que la lettre soit capitale ou non va dans le même sens et aide à la mémorisation.

• o-micron : on peut lire $f(n) \in O(g(n))$ et $f(n) \in o(g(n))$ comme «O-plus petit que» et «o-plus petit que», respectivement. Le suffixe «micro» signifie que plus on modifie le paramètre d'entrée, plus $f$ croît à une vitesse qui est plus petite que celle de $cg$. Suivant la casse de o (minuscule ou majuscule), c est un réel quelconque (domination en petit o) ou particulier (domination en grand o).
• o-mega : on peut lire $f(n) \in \Omega(g(n))$ et $f(n) \in \omega(g(n))$ comme «$\Omega$-plus grand que» et «$\omega$-plus grand que» et signifie : pour des valeurs très grandes du paramètre d'entrée, $f$ croît à une vitesse qui est plus grande que $cg$. Suivant la casse de $\omega$, c est un réel quelconque (soumission en $\Omega$) ou particulier (soumission en $\omega$).

Après grand-O, les notations Θ et Ω sont les plus utilisées en informatique ; le petit-o est courant en mathématiques mais plus rare en informatique. Le ω est peu usité.

Une autre notation parfois utilisée en informatique est Õ (soft-O en anglais) qui signifie grand-o à un facteur logarithmique près.

Notations de Landau, notations de Hardy, notation de Vinogradov

Notations de Landau

Les notations de Landau portent le nom du mathématicien allemand spécialisé en théorie des nombres Edmund Landau qui utilisa le symbole $O$ introduit primitivement par Paul Bachmann, et s'en inspira pour inventer le symbole $o$. Il n'utilisa le symbole $\Omega$ que dans un seul article en 1924 , pour signifier $\not=o$ ; cette notation avait été introduite (avec la même signification) en 1914 par G. H. Hardy et J. E. Littlewood  ; depuis, $\Omega$ est couramment utilisée en théorie des nombres, mais exclusivement dans ce même sens, et jamais dans le premier sens indiqué dans le tableau ci-dessus. Dans le même article Landau introduit les symboles $\Omega_R$ et $\Omega_L$ (depuis notés $\Omega_+$ et $\Omega_-$) pour signifier $\not<o$, respectivement $\not>o$ . Il utilise bien sûr également la notation $\sim$, mais jamais $\omega$ ou $\Theta$.

La lettre O est utilisée parce que la course de la « croissance » d'une fonction est aussi appelée l'ordre.

On utilise couramment la notation petit o pour dénoter le caractère négligeable d'une fonction et la notation grand O pour dénoter le caractère dominé d'une fonction par rapport à une autre fonction.

Les notations de Hardy sont désuètes. On notera d'ailleurs que Hardy utilise les notations de Landau dans tous ses articles (soit près de 400 !) et dans ses livres , sauf dans un tract de 1910 et dans 3 articles (1910-1913). La notation $\ll$ de Vinogradov, en revanche, est couramment utilisée en théorie des nombres à la place de $O$; parfois même les deux notations sont utilisées indifféremment dans le même article.

Notations de Hardy

Les notations de Hardy $\preceq$ et $\prec$, introduites par G. H. Hardy dans son tract de 1910 "Orders of Infinity", jouent le même rôle que celles de Landau pour la comparaison asymptotique des fonctions.

En notation de Landau, on peut les définir comme suit :

$f\preceq g \iff f \in O(g)$

et

$f\prec g \iff f\in o(g)~.$

(Notons que si Hardy a introduit dans son tract de 1910 quelques autres symboles pour la comparaison asymptotique des fonctions, il n'a par contre jamais défini ou utilisé la notation $\ll$, ni $\prec\!\!\prec$, comme il a été parfois affirmé).

Notation de Vinogradov

Le théoricien des nombres russe Ivan Matveyevich Vinogradov introduisit dans les années 1930 la notation qui porte son nom,

$f\ll g \iff f \in O(g)$.

Articles connexes

• Fonction asymptotique
• Vitesse de convergence des suites

Liens externes

• Big-O Cheat Sheet, un site répertoriant une classification des complexités algorithmiques par domaine.