Voir la source de Comparaison asymptotique

[[Fichier:Comparison computational complexity.svg|vignette|Comparaison asymptotique des fonctions utilisées en informatique plus précisément en algorithme. On voit par exemple que la fonction exponentielle (<math>2^n</math>) croit plus vite que la fonction linéaire (<math>n</math>).]]
En [[mathématiques]], plus précisément en [[analyse (mathématiques)|analyse]], la '''comparaison [[Asymptote|asymptotique]]''' est une méthode consistant à étudier la vitesse de croissance d'une [[Fonction (mathématiques)|fonction]]. 

Par exemple, la [[fonction exponentielle]] croit plus vite qu'une [[Fonction linéaire (analyse)|fonction linéaire]]. 

La comparaison asymptotique permet aussi d'étudier la vitesse d'une fonction quelconque par rapport à une fonction considérée comme plus « simple ». Celle-ci est souvent choisie sur une [[Échelle de comparaison|échelle de référence]], contenant  en général au moins certaines [[Fonction élémentaire|fonctions dites élémentaires]], en particulier les sommes et produits de [[polynôme]]s, d'[[Exponentielle de base a|exponentielles]] et de [[logarithme]]s<ref name="HSymboles">{{en}} G. H. Hardy, « The "Infinitärcalcül" of [[Paul David Gustave du Bois-Reymond|Paul du Bois-Reymond]] », Cambridge Tracts in Mathematics, 12, 1910, deuxième édition 1924. [http://www.gutenberg.org/files/38079/38079-pdf.pdf Lire en ligne] {{pdf}}.</ref>. La comparaison s'effectue en l'infini ou alors au [[Voisinage (mathématiques)|voisinage]] d'un point.

Le concept de comparaison asymptotique est utilisé en [[physique]]{{Référence nécessaire}}. Il l'est aussi en [[informatique]], par exemple pour décrire la [[Théorie de la complexité (informatique théorique)|complexité de certains algorithmes]]<ref>{{Ouvrage|langue=fr|titre=Algorithmique|date=2023-09-09|lire en ligne=https://www.dunod.com/sciences-techniques/algorithmique-cours-avec-957-exercices-et-158-problemes|consulté le=2023-09-09}}</ref>. En effet, la comparaison asymptotique est intéressante en l'infini, car on s'intéresse au comportement d'un algorithme sur des données arbitrairement grandes. Cette méthode de comparaison est également employée en [[théorie analytique des nombres]] pour évaluer finement l'erreur commise en remplaçant une fonction irrégulière, comme [[Fonction de compte des nombres premiers|celle comptant les nombres premiers]], par une fonction de l'échelle choisie.

La méthode a été introduite par les travaux de [[Paul David Gustave du Bois-Reymond|Paul du Bois-Reymond]] à partir de 1872<ref name="HSymboles" /> ; pour faciliter les calculs et la présentation des résultats, diverses [[#Notations de Landau, notations de Hardy, notation de Vinogradov|notations]] ont été développées, en particulier par [[Paul Bachmann|Bachmann]] (1894), [[Edmund Landau|Landau]] (1909), [[Godfrey Harold Hardy|Hardy]] (1910), Hardy et [[John Edensor Littlewood|Littlewood]] (1914 et 1916), et [[Ivan Vinogradov|Vinogradov]] ({{circa}} 1930).

== Exemples de comparaison ==

=== La relation de prépondérance ===
{{Article détaillé|Négligeabilité}}

==== Exemple ====
Soit {{math|''f''}} et {{math|''g''}} les fonctions réelles définies par les formules{{retrait|<math>f(x)=\cos(x)+2\text{ et }g(x)=x.</math>}}

Par une étude des deux fonctions, on sait que {{math|''g''}} prend des valeurs aussi grandes que l'on veut au voisinage de l'infini, tandis que {{math|''f''}} ne peut prendre des valeurs qu'entre 1 et 3. Le quotient {{math|''g''}} divisé par {{math|''f''}} au voisinage de l'infini ne cesse d'augmenter et n'est pas borné. Dans ce contexte, on peut dire que {{math|''f''}} est '''négligeable''' devant {{math|''g''}}, ou que {{math|''g''}} est '''prépondérante''' devant {{math|''f''}}, au voisinage de l'infini, on écrit (notation de Landau<ref name=Landau />) : <center><math>f(x) = o(g(x)) \ (x\rightarrow\infty)</math> </center> ou (notation de Hardy<ref name=HSymboles />{{,}}<ref name=HardyWright>{{HardyWright}}, {{4e}} éd., {{p.|7}}.</ref>, désuète<ref>Quoique toujours mentionnée dans la {{4e|édition}} du Hardy and Wright, p. 7, comme étant ''occasionnellement'' utilisée, elle n'est en fait ''jamais'' employée dans la suite de l'ouvrage, où les auteurs recourent systématiquement à la notation équivalente ''o''. Hardy lui-même n'a plus jamais utilisé cette notation dans ses travaux publiés après 1913.</ref>)
<center><math>f (x) \prec g(x)\ (x\rightarrow\infty).</math></center>

La notation de Hardy permet d'enchaîner les relations de prépondérance, par exemple :
<center><math>\cos (x) \prec \ln(x) \prec x \prec x^2\prec \exp(x) \prec x^x\ (x\rightarrow\infty).</math></center>

==== Définition formelle lorsque la fonction ''g'' ne s'annule pas ====
Pour définir formellement cette propriété on considère le comportement du quotient <math>\frac f g</math>.

Soit <math>a \in\R\cup \left\{ +\infty ; -\infty \right\}.</math>

Soient {{math|''f''}} et {{math|''g''}} deux fonctions de la variable réelle {{math|''x''}}. On suppose que {{math|''g''}} ne s'annule pas sur un voisinage de ''a''{{Note|texte=Pour éviter cette condition, on peut remplacer la définition qui suit par "On dit que <math>f(x) = \underset{ \overset { x \rightarrow a } {} } {o} (g(x))</math>, s'il existe une fonction <math>\epsilon (x)</math> telle que <math>f(x)=\epsilon (x)g(x)</math> et <math>\lim_{x\to a}\epsilon (x)=0</math>" ; mais cet élargissement de la définition n'a que peu d'intérêt pratique.}}. On dit que {{math|''f''}} est négligeable devant {{math|''g''}}, ou que {{math|''g''}} est '''prépondérante'''<ref>E. Ramis, C. Deschamp et J. Odoux, ''Cours de mathématiques spéciales'', tome 3, p. 148</ref> devant {{math|''f''}} en {{math|''a''}}, et on note <math>f(x) = \underset{ \overset { x \rightarrow a } {} } {o} (g(x))</math>, lorsque <center><math>\frac {f(x)} {g(x)} \underset{ \overset { x \rightarrow a } {} } {\longrightarrow} 0.</math></center>

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

Dans cette notation de Landau <math>f(x) = o(g(x))</math> (parfois aussi <math>f(x) \in o(g(x))</math>), le symbole <math>o</math> se lit ''petit o''. La notation équivalente de Hardy est <math>f(x) \prec g(x)</math>. On utilise aujourd'hui exclusivement la notation de Landau.

==== Propriétés ====
Par ce qui peut sembler un [[abus de langage]], on effectue des opérations sur les {{Citation|petits o}}. En effet, on peut écrire :
* <math>o(f) + o(f) = o(f)</math> ;
* <math>o(f) - o(f) = o(f)</math>.
Dans les côtés gauche de chaque formule les deux symboles <math>o(f)</math> représentent des fonctions a priori différentes. La première formule se lit : "la somme de deux fonctions qui sont toutes deux des petits <math>o(f)</math> est une fonction qui est également un <math>o(f)</math>".

==== Exemples ====

*<math> x^2 + 10000 = \underset{ \overset { x \rightarrow \infty } {} } {o} (x^3) </math>
* <math> x^n = \underset{ \overset { x \rightarrow +\infty } {} } {o} (e^x) </math>
* Pour toute fonction <math>\varepsilon</math>, telle que <math> \varepsilon (x) \underset{ \overset { x \rightarrow a } {} } {\longrightarrow} 0 </math>, on a : <math>\varepsilon (x) = \underset{ \overset { x \rightarrow a } {} } {o} (1)</math>

=== Équivalence ===
{{Article détaillé|Équivalent}}

==== Définition formelle ====
Soit <math>a \in\R\cup \left\{ +\infty ; -\infty \right\}</math>.

Soient {{math|''f''}} et {{math|''g''}} deux fonctions de la variable réelle {{math|''x''}}. On suppose que {{math|''g''}} ne s'annule pas sur un voisinage de {{math|''a''}}. On dit que {{math|''f''}} est équivalente à {{math|''g''}} en {{math|''a''}}, ou que {{math|''g''}} équivaut à {{math|''f''}} en {{math|''a''}}, et on note
:<math>f(x) \underset{ \overset { x \rightarrow a } {} } {\sim} g(x)</math>, lorsque <math> f(x) - g(x) = \underset{ \overset { x \rightarrow a } {} } {o} (g(x)) </math>.

==== Exemple ====
<math>\cos x + x^{20} + \exp(x) \underset{ \overset { x \rightarrow \infty } {} } {\sim} \exp(x)</math>

=== Domination ===

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 (lettre)|O]] [[Capitale et majuscule|majuscule]] (de l'allemand ''{{lang|de|Ordnung}}'', « ordre »). C'est beaucoup plus tard (1976), par analogie avec le symbole [[oméga]] majuscule Ω (voir plus bas), que [[Donald Knuth]] a discrètement suggéré de rebaptiser le symbole O du nom de la lettre [[omicron]] majuscule<ref name="knuth" /> (qui n'apparaît que dans le titre de son article), celle-ci étant rarement dessinée de manière clairement différente du O. Dans les deux cas, le symbole utilisé est distinct du symbole 0 (zéro).
==== Définition formelle ====

Soient {{math|''f''}} et {{math|''g''}} deux fonctions de la variable réelle {{math|''x''}}. On dit que {{math|''f''}} est dominée par {{math|''g''}} en {{math|+∞}}, ou que {{math|''g''}} domine {{math|''f''}} en {{math|+∞}}, et on note (notation de Bachmann, 1894, ou de Landau, 1909)
:<math>f(x)=O(g(x)) \ (x\rightarrow\infty),</math>
ou (notation de Hardy<ref name=HSymboles />, 1910, désuète)
:<math>\ f\preccurlyeq g, </math>
ou encore (notation de Vinogradov, années 1930)
:<math>f(x)\ll g(x) \ (x\rightarrow\infty),</math>
lorsqu'il existe des constantes {{math|''N''}} et {{math|''C''}} telles que
:<math>\forall x>N\qquad \left|f(x)\right| \le C \left|g(x)\right|.</math>
Intuitivement, cela signifie que {{math|''f''}} ne croît pas plus vite que {{math|''g''}}.

De même, si {{math|''a''}} est un [[nombre réel]], nous écrivons
:<math>f(x)=\underset{x\to a}O(g(x))</math>
s’il existe des constantes {{math|''d'' > 0}} et {{math|''C''}} telles que
:<math> \forall x \qquad \left|x - a\right| < d \Rightarrow \left|f(x)\right| \le C \left|g(x)\right|.</math>
Ceci est équivalent, lorsque {{math|''g''}} ne s'annule pas, à 
<math>\limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| < \infty.</math>

==== Exemples ====
* <math>4x^3 + 10000 x^2=\underset{x\to\infty}O(x^3).</math>
* <math>x^3 =\underset{x\to\infty}O(4x^3+ 10000 x^2).</math>
* En un point {{math|''a''}}, si {{math|''f''}} est négligeable devant {{math|''g''}} ou équivalente à {{math|''g''}}, alors elle est dominée par {{math|''g''}}.
* Une fonction {{math|''f''}} est [[Fonction bornée|bornée]] sur un voisinage de {{math|''a''}} si et seulement si <math>f(x)=\underset{x\to a}O(1)</math>.

== Absence de prépondérance et oscillations ==

=== Notation Ω de Hardy et Littlewood (théorie des nombres) ===
En 1914, [[Godfrey Harold Hardy|Hardy]] et [[John Edensor Littlewood|Littlewood]] ont introduit le nouveau symbole Ω<ref name="HL">{{en}} G. H. Hardy et J. E. Littlewood, « Some problems of Diophantine approximation », ''[[Acta Mathematica]]'', vol. 37, 1914, p. 225</ref> défini ainsi :

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

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

En 1916, les mêmes auteurs introduisent les deux nouveaux symboles Ω{{ind|''R''}} et Ω{{ind|''L''}}<ref name="HL2">{{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, 1916.</ref>, définis de la façon suivante :

:<math>f(x)=\Omega_R(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0</math>;

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

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

Contrairement à ce qu'affirmera plus tard [[Donald Knuth|D.E. Knuth]]<ref name="knuth">{{en}} Donald Knuth, « {{Langue|en|Big Omicron and big Omega and big Theta}} », ''[[SIGACT]] News'', avril-juin 1976, p. 18-24 {{Lire en ligne|url=http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf}} {{pdf}}.</ref>, [[Edmund Landau]] a également utilisé ces trois symboles en 1924<ref name="landau">{{de}} E. Landau, « Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV », ''Nachr. Gesell. Wiss. Gött. Math-phys. Kl.'', 1924, p. 137-150</ref>.

Ces notations de Hardy et Littlewood sont des prototypes, qui après Landau semblent n'avoir jamais été utilisés tels quels : [[#Notations de Landau|Ω{{ind|''R''}} est devenu Ω{{ind|+}}, et Ω{{ind|''L''}} est devenu Ω{{ind|–}}]].

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

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

=== Exemples ===

On a

:<math>\sin x=\Omega(1)\ (x\rightarrow\infty)</math>

et plus précisément,

:<math>\sin x=\Omega_\pm(1)\ (x\rightarrow\infty).</math>

On a

:<math>\sin x+1=\Omega(1)\ (x\rightarrow\infty)</math>

et plus précisément,

:<math>\sin x+1=\Omega_+(1)\ (x\rightarrow\infty)~;</math>

cependant,

:<math>\sin x+1\not=\Omega_-(1)\ (x\rightarrow\infty).</math>

=== Deux définitions incompatibles ===

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

:<math>f(x)=\Omega(g(x))\ (x\rightarrow\infty)</math>

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é (informatique théorique)|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 ===

En 1976, [[Donald Knuth|Knuth]] publie un article<ref name="knuth"/> 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<ref name="titchmarsh">{{en}} E. C. Titchmarsh, ''The Theory of the Riemann Zeta-Function'', Oxford, Clarendon Press, 1951</ref>). Il va jusqu'à prétendre que Landau ne l'a jamais utilisée (ce qui est également faux<ref name="landau" />). Il ressent impérativement le besoin d'une autre notion ({{Citation étrangère|langue=en|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 ({{Citation étrangère|langue=en|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

:<math>f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))</math><ref> Il se justifie en écrivant : {{Citation étrangère|langue=en|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.}}</ref>.

== 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éveloppement limité|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 :
:<math> e^x = 1+x+\frac{1}{2} x^2+o(x^2) \ {\rm quand}\  x \rightarrow 0</math>
pour exprimer le fait que l'erreur, la différence <math>e^x - \left(1 + x +\frac{x^2}{2}\right)</math>, est négligeable devant <math>x^2</math> quand <math>x</math> tend vers 0.

Il faut préciser que le nombre d'[[opérande]]s dans ce genre d'écriture doit être borné par une constante qui ne dépend pas de la variable : par exemple l'assertion <math>o(x)+o(x)+\dots+o(x)=o(x)</math> est évidemment fausse si les points de suspension cachent un nombre de termes qui n'est pas borné lorsque ''x'' varie.

=== Échelle de comparaison ===
Voici une liste de catégories de fonctions couramment utilisées [[Analyse (mathématiques)|en analyse]]. La variable (notée ici ''n'') tend vers {{math|+∞}} et ''c'' est une constante réelle arbitraire. Lorsque ''c'' est une constante supérieure à 1, les fonctions apparaissent dans cette liste par ordre croissant de grandeur.

<center>
{|
|-----
| '''notation''' || || '''grandeur au plus'''
|-----
| O(1) || || module majoré par une [[constante]]
|-----
| O(log(''n'')) || || [[logarithme|logarithmique]]
|-----
| O((log(''n''))''{{exp|c}}'') || || ([[polylogarithmique]] si ''c'' est entier positif)
|-----
| O(''n'') || || [[Linéarité|linéaire]]
|-----
| O(''n'' log(''n'')) ||
| parfois appelée « [[linéarithmique]] »
|-----
| O(''n log{{exp|c}}(n)'') ||
| parfois appelé « [[quasi linéaire]] » 
|-----
| O(''n''{{2}}) || || [[Convergence quadratique|quadratique]]
|-----
| O(''n{{exp|c}}'') ||
| ([[polynôme|polynomiale]] si ''c'' est entier positif)
|-----
| O(''c{{exp|n}}'') || || ([[croissance exponentielle|exponentielle]] si ''c'' est positif, parfois « [[progression géométrique|géométrique]] »)
|-----
| O(''n!'') || || [[factorielle]]
|}
</center>

O(''n{{exp|c}}'') et O(''c{{exp|n}}'') 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 ''n''<sup>log(''n'')</sup>.

Remarquons aussi que O(log ''n'') est exactement identique à O(log(''n{{exp|c}}'')), puisque ces deux [[logarithme]]s sont multiples l'un de l'autre par un [[Facteur (mathématiques)|facteur]] constant et que la notation grand O « ignore » les [[constante]]s 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 [[fonction (mathématiques)|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'').

Exemple :
:: si ''f''(''n'') = 10 log(''n'') + 5 (log(''n'')){{3}} + 7 ''n'' + 3 ''n''{{2}} + 6 ''n''{{3}},<br/> alors ''f''(''n'') = O(''n''{{3}}).
{{article détaillé|Échelle de comparaison}}

=== Fonction à plusieurs variables ===

Cette notation peut aussi être utilisée avec des [[Fonction de plusieurs variables|fonctions de plusieurs variables]] :
<center>
{|
|L'écriture :
|<math>f(n,m) = n^2 + m^3 + O(n+m)\;</math> quand <math>m,n\to +\infty</math>
|-
|correspond à la proposition :
|<math>\exists C \quad \exists N \quad \forall n,m > N \qquad  |f(n,m) -n^2-m^3 |\le C(n+m) </math>
|}
</center>
Pour certains, cette notation abuse du [[symbole]] d'égalité, puisqu'elle semble violer l'[[Logique#Égalité|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]]). Mais on peut également considérer que dans l'écriture
<center><math>f(n,m) - n^2 - m^3 = O(n+m),</math></center>
la notation "=O" désigne un seul opérateur, dans l'écriture duquel le signe "=" n'a pas d'existence propre indépendante (et en particulier ne désigne pas une relation d'équivalence). Il n'y a dans ce cas plus d'abus de notation, mais évidemment toujours un risque de confusion. Il est également 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 {{math|''g''}}, et d'utiliser les notations ensemblistes pour indiquer si une fonction donnée est un élément de l'ensemble ainsi défini. Par exemple :
<center><math>f(n,m) - n^2 - m^3 \in O(n+m),</math></center>
Les deux conventions sont couramment utilisées mais la première (et plus ancienne) est jusqu'au début du {{S-|XXI}} la plus souvent rencontrée. Pour éviter ce problème on utilise (tout aussi couramment) la notation de Vinogradov (voir ci-dessous).
<center><math>f(n,m) - n^2 - m^3 \ll n+m,</math></center>

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

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

{|class="wikitable centre"
!Notation
!width="100pt"|Nom
!|Description informelle
!Lorsque <math> n \to \infty</math>, à partir d'un certain rang...
!Définition rigoureuse
<!-- !Autre définition -->
|-
|<math>f(n) = O(g(n))</math>

ou

<math>f(n) \in O(g(n))</math>
|width="100pt"|Grand O<br/> (Grand Omicron<ref name="knuth"/>)
|
La fonction |{{math|''f''}} | est bornée par la fonction |{{math|''g''}}| asymptotiquement,<br/> à un facteur près
<!-- |Dans ces notations, g(''n'') est supposée positive à l'infini. <math>\limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty</math> -->
|<math>|f(n)|  \leq  |g(n)|\cdot k</math> pour un ''k'' > 0
|<math>\exists k>0, \exists n_0 \; \forall n>n_0 \; |f(n)| \leq |g(n)|\cdot k </math><!--<br/>  ou<br/>  <math>  \exists k>0, n_0 \; \forall n>n_0 \; f(n) \leq g(n)\cdot k</math>-->
|-
|rowspan=2|<math>f(n) = \Omega(g(n))</math>

ou

<math>f(n) \in \Omega(g(n))</math>
|width="100pt"rowspan=2|Grand Omega
|'''Deux définitions : '''

En théorie des nombres :<br />{{math|''f''}} n'est pas négligeable {{nowrap|devant {{math|''g''}}}}
|
En théorie des nombres :

<math>|f(n_i)|  \geq  |g(n_i)|\cdot k</math> pour un ''k'' > 0<br/> et
pour une  suite de nombres <math> n_i\rightarrow\infty</math>
<!--|Dans ces notations, g(''n'') est supposée positive à l'infini. <math>\liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 </math> -->

|
En théorie des nombres :

<math>\exists k>0, \forall n_0 \; \exists n>n_0 \; |g(n)|\cdot k \leq |f(n)|</math>
|-

| En théorie des algorithmes : 

{{math|''f''}} est minorée par {{math|''g''}}  (à un facteur près)<br/>(ou ''f'' domine ''g'')
    
|En théorie des algorithmes :

<math>|f(n)|  \geq  |g(n)|\cdot k</math> pour un ''k'' > 0 

|En théorie des algorithmes :

<math>\exists k>0, \exists n_0 \; \forall n>n_0 \; |g(n)|\cdot k \leq |f(n)|</math>
|-
|<math>f(n)\asymp g(n)</math>

ou

<math>f(n) \in \Theta(g(n))</math>
|width="100pt"|de l'ordre de ;<br/> Grand Theta
|Les fonctions {{math|''f''}} et {{math|''g''}} sont du même ordre de grandeur asymptotiquement
|<math>|g(n)|\cdot k_1 \leq |f(n)| \leq |g(n)|\cdot k_2</math><br/> pour un ''k''<sub>1</sub> > 0, et un ''k''<sub>2</sub>  > 0
<!-- |<math>0 < \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| \leq \limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right|< \infty</math> -->
<!--|<math>f(n) \in O(g(n)) \cap \Omega(g(n))</math> -->
|<math>\exists k_1,k_2>0, \exists n_0 \; \forall n>n_0</math><br/><math> |g(n)|\cdot k_1 < |f(n)| < |g(n)|\cdot k_2 </math>
|-
|<math>f(n) = o(g(n))</math>

ou

<math>f(n) \in o(g(n))</math>
|width="100pt"|Petit o  
|{{math|''f''}} est négligeable devant {{math|''g''}} asymptotiquement
|<math>|f(n)| \le |g(n)|\cdot \varepsilon</math>, quel que soit <math>\varepsilon</math> > 0 (fixé).
<!-- |<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = 0</math> -->
<!-- |<math>\forall \;\epsilon>0,\exists \;n(\epsilon) : |f(n)| < \; \epsilon |g(n)|, \forall n>n(\epsilon).</math> -->
|<math>\forall \varepsilon>0 \; \exists n_0 \; \forall n>n_0 \; |f(n)| \le |g(n)|\cdot \varepsilon</math>
|-
|<math>f(n) \in \omega(g(n))</math>
|width="100pt"|Petit Omega
|{{math|''f''}} domine {{math|''g''}} asymptotiquement
|<math>|f(n)| \ge |g(n)|\cdot k</math> pour tout ''k'' > 0
<!-- |<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = \infty</math> -->
|<math>\forall k>0 \; \exists n_0 \; \forall n>n_0 \; |g(n)|\cdot k \le |f(n)|</math>
<!-- Sometimes this is expressed as "\forall M<\infty" - any preference here? -->
|-
|<math>f(n)\sim g(n)\!</math><!-- force PNG; ~ is often ugly -->
|width="100pt"|équivalent à
|{{math|''f''}} est approximativement égale à {{math|''g''}} asymptotiquement
|<math>|f(n)-g(n)|<\varepsilon |g(n)| </math>, quel que soit <math>\varepsilon</math> > 0 (fixé).
|<math>\forall \varepsilon>0\;\exists n_0\;\forall n>n_0\;|f(n)-g(n)|<\varepsilon |g(n)|</math>
|}

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 poly-logarithmique près. Autrement dit,  f(n) = Õ(g(n)) signifie qu'il existe un entier k tel que f(n) = O(g(n) log<sup>k</sup> g(n)).

La notation ''f''(''x'')<math>\asymp</math>''g''(''x''), introduite par Hardy en 1910<ref name="HSymboles"/>, est couramment utilisée en théorie des nombres<ref name=HardyWright/>{{,}}<ref>{{Ouvrage|auteur1=Gérald Tenenbaum|titre=Introduction à la théorie analytique et probabiliste des nombres|passage=|éditeur=Belin|date=2008|numéro chapitre=|titre chapitre=Notations}}.</ref>. Elle a la même signification que ''f''(''x'') = Θ(''g''(''x'')), proposée par Knuth en 1976<ref name="knuth" />.

== Systèmes de notations ==

=== 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''<ref name=Landau>{{de}} Edmund Landau, ''Handbuch der Lehre von der Verteilung der Primzahlen'', Berlin 1909, p. 883.</ref>, introduit primitivement par [[Paul Bachmann]]<ref>''{{Lang|de|Zahlentheorie}}'', tome 2, 1894, p. 402.</ref>, et s'en inspira pour inventer le symbole ''o''.
Il n'utilisa le symbole Ω que dans un seul article en 1924<ref name="landau" />, pour signifier ≠ ''o ''; cette notation avait été introduite (avec la même signification) en 1914 par G. H. Hardy et J. E. Littlewood<ref name="HL" /> ; 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 Ω{{ind|''R''}} et Ω{{ind|''L''}}, également dus à Hardy et Littlewood<ref name="HL2" />, (et depuis notés Ω{{ind|+}} et Ω{{ind|–}})
pour signifier <math> \not<o </math>, respectivement <math> \not>o </math>. Il utilise bien sûr également la notation ∼, mais jamais ω ou Θ.

=== Des notations de Hardy ===
Les notations de Hardy <math> \preccurlyeq </math> et <math> \prec </math>, introduites par [[G. H. Hardy]] dans son tract de 1910 ''Orders of Infinity''<ref name=HSymboles /> (parmi d'autres notations), 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 :
:<math> f\preccurlyeq g \iff f = O(g) </math>
et
:<math> f\prec g \iff f = o(g).</math>

Ces notations de Hardy sont désuètes et Hardy lui-même les a rapidement abandonnées ; il utilise les notations de Landau dans tous ses articles (soit près de 400 !) et dans ses livres<ref>Voir par exemple {{HardyWright}}.</ref>  sauf dans son tract de 1910 et dans 3 articles (1910-1913). On peut noter 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 <math> \ll </math> (ou <math> \prec\!\!\prec </math>), qu'on doit à Vinogradov.

=== Notation de Vinogradov ===

Le théoricien des nombres russe [[Ivan Vinogradov|Ivan Matveyevich Vinogradov]] introduisit dans les années 1930<ref>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.</ref> la notation qui porte son nom,

:<math> f\ll g \iff f = O(g) </math>.

La notation ≪ de [[Ivan Vinogradov|Vinogradov]] 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.

=== Notation L ===
{{Article détaillé|Notation L}}
En 1982, [[Carl Pomerance]] a introduit une nouvelle notation pour abréger les fonctions complexes intervenant dans l'étude asymptotique de la [[Analyse de la complexité des algorithmes|complexité des algorithmes]]. Ainsi, par exemple, une fonction  ''f''  appartient à la classe <math>L_n[\alpha, c] </math> si on a <math>f = \exp\left((c + o(1)) \log(n)^{\alpha} (\log \log n)^{1-\alpha} \right)</math> ; l'exponentielle « écarte » suffisamment  les fonctions pour qu'il ne soit pas possible de ramener cette notation à la forme <math>f=O(g)</math> par exemple.

== Notes et références ==
{{Traduction/Référence|en|Big O notation|1080680|type=note}}
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Développement asymptotique]]
* [[Fonction asymptotique]]
* [[Vitesse de convergence des suites]]
*[[Échelle de comparaison]] 
*[[Combinatoire analytique]]

=== Lien externe ===
{{en}} [http://bigocheatsheet.com/ Big-O Cheat Sheet], un site répertoriant une classification des complexités algorithmiques par domaine.

{{Portail|analyse}}

[[Catégorie:Analyse réelle]]
[[Catégorie:Vocabulaire des mathématiques]]
[[Catégorie:Théorie analytique des nombres]]