Comparaison asymptotique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 réputée « simple » et « connue », souvent choisie sur une échelle de référence. Cette échelle comprend en général les fonctions constructibles par somme, produit, élévation à une puissance réelle, différentiation et intégration de monômes, d'exponentielles et de logarithmes. 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. Elle est également utilisée en théorie analytique des nombres pour évaluer finement l'erreur commise lors de la détermination de l'ordre moyen d'une fonction arithmétique, un exemple célèbre étant le théorème des nombres premiers.

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

Exemples de comparaison[modifier | modifier le code]

La relation de prépondérance[modifier | modifier le code]

Article détaillé : Fonction négligeable.

Exemple[modifier | modifier le code]

Soit f et g les fonctions réelles définies par les formulesf(x)=\cos(x)+2\text{ 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[modifier | modifier le code]

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

Soit a \in\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[1] 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[modifier | modifier le code]

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[modifier | modifier le code]

  •  x^2 + 2014 = \underset{ \overset { x \rightarrow \infty } {} } {o} (x^3)
  •  x^n = \underset{ \overset { x \rightarrow +\infty } {} } {o} (e^x)
  • 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[modifier | modifier le code]

Article détaillé : Équivalent.

Définition formelle[modifier | modifier le code]

Soit a \in\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[modifier | modifier le code]

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

Domination[modifier | modifier le code]

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

Généralement, comme Paul Bachmann qui a introduit ce symbole en 1894, on utilise la lettre O majuscule ("Ordnung"). C'est beaucoup plus tard (1976), par analogie avec le symbole Omega majuscule Ω (voir plus bas), que Donald Knuth a proposé de rebaptiser le symbole O du nom de la lettre omicron majuscule[2], celle-ci étant rarement dessinée de manière clairement différente du O. Surtout ne pas employer le chiffre zéro.

Définition formelle[modifier | modifier le code]

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 \Rightarrow \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[modifier | modifier le code]

  • 4x^3 + 2014 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).

Absence de prépondérance et oscillations[modifier | modifier le code]

Notation Ω de Hardy et Littlewood (théorie des nombres)[modifier | modifier le code]

En 1914, Hardy et Littlewood ont introduit le nouveau symbole Ω[3] défini ainsi :

f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0.

Les fonctions f et g sont supposées définies, et g positive, dans un voisinage de l'infini. Ainsi f(x)=\Omega(g(x)) est la négation de f(x)=o(g(x)).

En 1918, les mêmes auteurs introduisent les deux nouveaux symboles ΩR et ΩL[4], définis de la façon suivante :

f(x)=\Omega_R(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0;
f(x)=\Omega_L(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\liminf_{x \to \infty} \frac{f(x)}{g(x)}< 0.

Comme avant, les fonctions f et g sont supposées définies, et g positive, dans un voisinage de l'infini. Ainsi, f(x)=\Omega_R(g(x)) est la négation de f(x)<o(g(x)), et f(x)=\Omega_L(g(x)) la négation de f(x)>o(g(x)).

Contrairement à ce qu'affirmera plus tard D.E. Knuth[2], Edmund Landau a également utilisé ces trois symboles en 1924[5].

Ces notations de Hardy et Littlewood sont des prototypes, qui après Landau semblent n'avoir jamais été utilisés tels quels : ΩR est devenu Ω+, et ΩL est devenu Ω.

Ces trois symboles sont maintenant couramment utilisés en théorie analytique des nombres, de même que f(x)=\Omega_\pm(g(x)) pour signifier que les conditions f(x)=\Omega_+(g(x)) et f(x)=\Omega_-(g(x)) sont toutes deux satisfaites.

Il est clair que dans chacune de ces définitions on peut remplacer par –∞ ou par un nombre réel.

Exemples simples[modifier | modifier le code]

On a

\sin x=\Omega(1)\ (x\rightarrow\infty)

et plus précisément,

\sin x=\Omega_\pm(1)\ (x\rightarrow\infty).

On a

\sin x+1=\Omega(1)\ (x\rightarrow\infty)

et plus précisément,

\sin x+1=\Omega_+(1)\ (x\rightarrow\infty)~;

cependant,

\sin x+1\not=\Omega_-(1)\ (x\rightarrow\infty).

Deux définitions incompatibles[modifier | modifier le code]

Il est important de souligner le fait que l'écriture

f(x)=\Omega(g(x))\ (x\rightarrow\infty)

possède en mathématiques deux définitions incompatibles, toutes les deux très répandues, l'une en théorie analytique des nombres, qu'on vient de présenter, l'autre en théorie de la complexité des algorithmes. Lorsque ces deux disciplines se rencontrent, cette situation est susceptible de créer une grande confusion.

La définition de Knuth[modifier | modifier le code]

En 1976, Knuth publie un article[2] dont le but principal est de justifier son utilisation du même symbole Ω pour décrire une autre propriété que celle décrite par Hardy et Littlewood. Il tente de convaincre le lecteur que la définition de Hardy et Littlewood n'est quasiment jamais utilisée (ce qui, même en 1976, est faux depuis en tout cas 25 ans[6]). Il va jusqu'à prétendre que Landau ne l'a jamais utilisée (ce qui est également faux[5]). Il ressent impérativement le besoin d'une autre notion (« For all the applications I have seen so far in computer science, a stronger requirement […] is much more appropriate »), et a décidé que l'utilisation du symbole Ω doit être réservé pour la décrire. Il est fortement contrarié par l'ancienne définition (« Unfortunately, Hardy and Littlewood didn't define Ω(f(n)) as I wanted to »).

Il prend donc le risque de créer la confusion, et définit

f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))[7].

Utilisation des comparaisons[modifier | modifier le code]

Développements limités[modifier | modifier le code]

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[modifier | modifier le code]

Voici une liste de catégories de fonctions couramment utilisées en analyse. La variable (notée ici n) tend vers +∞ et c est une constante réelle arbitraire. Lorsque c est une constante entière positive, les fonctions apparaissent dans cette liste par ordre croissant de grandeur.

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

O(nc) et O(cn) sont très différents. Le dernier autorise 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 dite superpolynomiale. Une fonction qui croît plus lentement que toute exponentielle est dite sous-exponentielle. Il existe des fonctions à la fois superpolynomiales et sous-exponentielles, comme la fonction nlog(n). Certains algorithmes ont un temps de calcul de ce type, comme[réf. souhaitée] celui[Lequel ?] de la factorisation d'un nombre entier.

Remarquons aussi que O(log n) est exactement identique à O(log(nc)), 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 croît plus vite que les autres, alors elle détermine l'ordre de croissance de f(n).

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

Fonction à plusieurs variables[modifier | modifier le code]

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 correct, il est possible de 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'au début du XXIe siècle la plus souvent rencontrée. Pour éviter ce problème on utilise (tout aussi 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, Ω, ω, Θ, ~[modifier | modifier le code]

Notation Nom Description informelle Lorsque  n \to \infty, à partir d'un certain rang... Définition rigoureuse
f(n) \in O(g(n)) Grand O
(Grand Omicron[2])

La fonction |f | est bornée par la fonction |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 Deux définitions :

En théorie des algorithmes :

f est minorée par g (à un facteur près)

En théorie des nombres :
f n'est pas négligeable devant g

En théorie des algorithmes :

|f(n)|  \geq  |g(n)|\cdot k pour un k > 0

En théorie des nombres :

|f(n_i)|  \geq  |g(n_i)|\cdot k pour un k > 0
et pour une suite de nombres  n_i\rightarrow\infty

En théorie des algorithmes:

\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 f est négligeable devant 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)|

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.

En théorie des nombres la notation f(x)\asympg(x) a la même signification que f(x) = Θ(g(x)) (qui n'est pas utilisée).

Notations de Landau, notations de Hardy, notation de Vinogradov[modifier | modifier le code]

Notations de Landau[modifier | modifier le code]

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[8], introduit primitivement par Paul Bachmann[9], et s'en inspira pour inventer le symbole o. Il n'utilisa le symbole Ω que dans un seul article en 1924[5], pour signifier ≠ o ; cette notation avait été introduite (avec la même signification) en 1914 par G. H. Hardy et J. E. Littlewood[3] ; depuis, Ω est couramment utilisé 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 utilise les symboles ΩR et ΩL, également dus à Hardy et Littlewood[4], (et depuis notés Ω+ et Ω) pour signifier  \not<o , respectivement  \not>o . Il utilise bien sûr également la notation ∼, mais jamais ω ou Θ.

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[10], sauf dans un tract de 1910 et dans 3 articles (1910-1913). La notation ≪ 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[modifier | modifier le code]

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[modifier | modifier le code]

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

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

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Big O notation » (voir la liste des auteurs)

  1. E. Ramis, C. Deschamp et J. Odoux, Cours de mathématiques spéciales, tome 3, p. 148
  2. a, b, c et d (en) Donald Knuth, « Big Omicron and big Omega and big Theta », SIGACT News, avril-juin 1976, p. 18-24 [lire en ligne]
  3. a et b (en) G. H. Hardy et J. E. Littlewood, « Some problems of Diophantine approximation », Acta Mathematica, vol. 37, 1914, p. 225
  4. a et b (en) G. H. Hardy et J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », Acta Mathematica, vol. 41, 1918.
  5. a, b et c (de) E. Landau, « Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV », Nachr. Gesell. Wiss. Gött. Math-phys. Kl., 1924, p. 137-150
  6. (en) E. C. Titchmarsh, The Theory of the Riemann Zeta-Function, Oxford, Clarendon Press, 1951
  7. Il se justifie en écrivant : « Although I have changed Hardy and Littlewood's definition of Ω, I feel justified in doing so because their definition is by no mean in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies. »
  8. (de) Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Berlin 1909, p. 883.
  9. Zahlentheorie, tome 2, 1894, p. 402.
  10. Voir par exemple (en) G. H. Hardy et E. M. Wright, An Introduction to the Theory of Numbers [détail des éditions].
  11. Voir par exemple « Une nouvelle estimation pour G(n) dans le problème de Waring » (en russe), Doklady Akademii Nauk SSSR, vol. 5, n° 5-6, 1934, p. 249-253. Traduction en anglais dans : Selected works / Ivan Matveevič Vinogradov ; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday, Springer-Verlag, 1985.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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