Notation Big O

notation mathématique qui décrit la taille approximative d'une fonction sur un domaine . Elle appartient à la famille des notations inventées par les mathématiciens allemands Paul Bachmann et Edmund Landau , puis développées par d'autres, et appelées collectivement notation de Bachmann-Landau . La lettre O signifie « Ordnung » , c'est-à-dire l' ordre d'approximation .

En informatique , la notation grand O est utilisée pour classer les algorithmes selon la façon dont leur temps d'exécution ou leurs besoins en espace mémoire évoluent en fonction des données d'entrée. En théorie analytique des nombres , la notation grand O exprime des bornes sur la croissance d'une fonction arithmétique , comme pour le reste du théorème des nombres premiers . En analyse mathématique , y compris en calcul différentiel et intégral , la notation grand O borne l'erreur lors de la troncature d'une série entière et exprime la qualité de l'approximation d'une fonction à valeurs réelles ou complexes par une fonction plus simple.

La notation grand O caractérise souvent les fonctions selon leur taux de croissance lorsque la variable devient grande : différentes fonctions ayant le même taux de croissance asymptotique peuvent être représentées par la même notation O. La lettre O est utilisée car le taux de croissance d'une fonction est également appelé son ordre . Une description d'une fonction en termes de notation grand O ne fournit qu'une borne supérieure de son taux de croissance.

Plusieurs notations apparentées, utilisant les symboles , , , , , , , et pour décrire d'autres types de bornes sur les taux de croissance, sont associées à la notation grand O.

Bachmann a proposé la notation en 1894 et Landau l'a étendue en 1909. Une notation antérieure a été proposée par Paul du Bois-Reymond en 1870.

réelles ou complexes définie sur un domaine , et soit la fonction de comparaison une fonction à valeurs réelles non négatives définie sur le même ensemble. Les domaines couramment choisis sont les intervalles de nombres réels, bornés ou non, l'ensemble des entiers positifs, l'ensemble des nombres complexes et les n-uplets de nombres réels/complexes. Le domaine étant défini explicitement ou implicitement, on écrit :

0, c > 0,

Exemples avec un domaine infini

En usage courant, cette notation s'applique à un intervalle infini de nombres réels et décrit le comportement de la fonction pour de très grandes valeurs de . Dans ce contexte, la contribution des termes qui croissent le plus rapidement finira par rendre les autres négligeables. Par conséquent, les règles de simplification suivantes peuvent être appliquées :

Si est une somme de plusieurs termes, s'il en existe un avec le taux de croissance le plus élevé, on peut le conserver et omettre tous les autres.
Si est un produit de plusieurs facteurs, toutes les constantes (facteurs du produit qui ne dépendent pas de ) peuvent être omises.

Par exemple, soit , et supposons que nous souhaitions simplifier cette fonction, en utilisant la notation , pour décrire son taux de croissance pour de grandes valeurs de . Cette fonction est la somme de trois termes : , , et . Parmi ces trois termes, celui qui a le taux de croissance le plus élevé est celui dont l'exposant est le plus grand en fonction de , à savoir . On peut alors appliquer la deuxième règle : est un produit de et dans lequel le premier facteur ne dépend pas de . En omettant ce facteur, on obtient la forme simplifiée . Ainsi, on dit que est un « grand O » de . Mathématiquement, on peut écrire pour tout . On peut vérifier ce calcul à l'aide de la définition formelle : soient et . En appliquant la définition formelle ci-dessus, l'affirmation est équivalente à son développement, pour un choix approprié d'un nombre réel positif et pour tout . Pour le prouver, soit . Alors, pour tout : donc . Bien qu'il soit également vrai, par le même raisonnement, que , il s'agit d'une approximation moins précise de la fonction . D'autre part, l'affirmation est fausse, car le terme rend non bornée.

Lorsqu'une fonction décrit le nombre d'étapes requises dans un algorithme avec une entrée , une expression telle que avec le domaine implicite étant l'ensemble des entiers positifs, peut être interprétée comme indiquant que l'algorithme a au plus une complexité temporelle de l'ordre de .

Exemple avec un domaine fini

La notation grand O peut également servir à décrire l' erreur d'approximation d'une fonction mathématique sur un intervalle fini. Les termes les plus significatifs sont explicitement écrits, puis les termes les moins significatifs sont regroupés dans une seule notation grand O. Prenons l'exemple de la série exponentielle et de deux expressions valides pour n petit : l'expression du milieu théorème de Taylor .

Le comportement d'une fonction donnée peut être très différent sur des domaines finis que sur des domaines infinis, par exemple, tandis que

Exemples multivariés

Nous avons ici une fonction complexe de deux variables. En général, toute fonction bornée est .

Le dernier exemple illustre un mélange de domaines finis et infinis sur les différentes variables.

Dans tous ces exemples, la borne est uniforme par rapport aux deux variables. Parfois, dans une expression multivariée, une variable est plus importante que les autres, et l'on peut indiquer que la constante implicite dépend d'une ou plusieurs variables en utilisant des indices pour le symbole grand O ou le symbole ε. Par exemple, considérons l'expression suivante :

Cela signifie que pour chaque nombre réel , il existe une constante , qui dépend de , de sorte que pour tout , Cette affirmation particulière découle du théorème binomial général .

Un autre exemple, courant dans la théorie des séries de Taylor , est le suivant : ici, la constante implicite dépend de la taille du domaine.

La convention d'indice s'applique à toutes les autres notations de cette page.

Propriétés

Produit

Somme

Si et alors . Il s'ensuit que si et alors .

Multiplication par une constante

Soit

propriété transitive

Si et alors .

Si la fonction d'un entier positif peut s'écrire comme une somme finie d'autres fonctions, alors celle qui croît le plus rapidement détermine l'ordre de . Par exemple,

Quelques règles générales concernant la croissance vers l'infini ; les 2e et 3e propriétés ci-dessous peuvent être démontrées rigoureusement à l'aide de la règle de L'Hôpital :

Les grandes puissances dominent les petites puissances

Car , alors comme .

Les puissances dominent les logarithmes

Pour toute valeur positive, quelle que soit la valeur de et quelle que soit la valeur de . Ici, la constante implicite dépend à la fois de et .

Les exponentielles dominent les puissances

Pour tout élément positif, quelle que soit son ampleur ou sa petitesse .

Une fonction qui croît plus rapidement que toute fonction exponentielle de la forme avec est dite superpolynomiale . Une fonction qui croît moins rapidement que toute fonction exponentielle de la forme avec est dite sous-exponentielle . Un algorithme peut avoir une complexité temporelle à la fois superpolynomiale et sous-exponentielle ; c’est le cas, par exemple, des algorithmes les plus rapides connus pour la factorisation d’entiers et de la fonction . $1 c > 1$

On peut négliger les puissances de n à l'intérieur des logarithmes. Pour tout n positif , la notation λ = λⁿ signifie exactement la même chose que λ = λⁿ , puisque λ = λⁿ. De même, les logarithmes ayant des bases constantes différentes sont équivalents du point de vue de la notation grand O. En revanche, les exponentielles ayant des bases différentes ne sont pas du même ordre de grandeur. Par exemple, λⁿ et λⁿ ne sont pas du même ordre de grandeur.

Expressions plus compliquées

Dans des cas plus complexes, l'opérateur peut apparaître à différents endroits d'une équation, voire plusieurs fois de chaque côté. Par exemple, les affirmations suivantes sont vraies pour un entier positif : La signification de ces affirmations est la suivante : pour toute fonction satisfaisant chaque condition du membre de gauche, il existe des fonctions satisfaisant chaque condition du membre de droite, de sorte que la substitution de toutes ces fonctions dans l'équation rend les deux membres égaux. Par exemple, la troisième équation ci-dessus signifie : « Pour toute fonction satisfaisant , il existe une fonction telle que ». La constante implicite dans l'affirmation « » peut dépendre de la constante implicite dans l'expression « ».

Voici quelques autres exemples : 0\\\\ \\sin x &= O(|x|) \\quad \ ext{ for all real } x. \\end{align} " $0\\\sin x&=O(|x|)\quad { ext{ for all real }}x.\end{aligned \begin{matrix} f = O (g) & \Rightarrow \int_{a}^{b} f = O (\int_{a}^{b} g) \\ f (x) = g (x) + O (1) & \Rightarrow e^{f (x)} = O (e^{g (x)}) \\ (1 + O (1 / x))^{O (x)} & = O (1) for x > 0 \\ \sin x & = O (| x |) for all real x . \end{matrix}$ 0\\\sin x&=O(|x|)\quad { ext{ pour tout }}x réel.\end{aligned

Le ≫ de Vinogradov et le grand Ω de Knuth

Lorsque f et g sont toutes deux des fonctions positives, Vinogradov a introduit la notation , qui signifie la même chose que . Les deux notations de Vinogradov présentent une symétrie visuelle, car pour les fonctions positives , on a

En 1976, Donald Knuth a défini

qui a la même signification que celle de Vinogradov .

Cependant, bien plus tôt, Hardy et Littlewood avaient défini différemment , et leur notation est aujourd'hui largement utilisée en théorie analytique des nombres. Justifiant son utilisation du symbole - pour décrire une propriété plus forte, Knuth a écrit : « Pour toutes les applications que j'ai vues jusqu'à présent en informatique, une exigence plus forte… est bien plus appropriée. » Knuth a ajouté : « Bien que j'aie modifié la définition de Hardy et Littlewood , je me sens justifié de le faire car leur définition est loin d'être largement répandue, et parce qu'il existe d'autres façons d'exprimer ce qu'ils veulent dire dans les cas relativement rares où leur définition s'applique. » La notation de Knuth est aujourd'hui largement utilisée en informatique et en combinatoire .

Le ≍ de Hardy et le grand Θ de Knuth

En théorie analytique des nombres, la notation signifie à la fois et . Cette notation est due à Hardy. La notation de Knuth pour la même notion est . En résumé, ces énoncés affirment que et ont le même ordre . Ces notations signifient qu'il existe des constantes positives telles que pour tout dans le domaine commun de . Lorsque les fonctions sont définies sur les entiers positifs ou les nombres réels positifs, comme avec la notation grand O, les auteurs interprètent souvent les énoncés et comme étant vrais pour tout suffisamment grand , c'est-à-dire pour tout au-delà d'un certain point . Parfois, cela est indiqué en ajoutant à l'énoncé. Par exemple, est vrai pour le domaine mais faux si le domaine est l'ensemble des entiers positifs, puisque la fonction est nulle en .

Autres exemples

La notation

$signifie qu'il existe une constante positive telle que pour tout . En revanche, signifie qu'il existe une constante positive telle que pour tout et signifie qu'il existe des constantes positives telles que pour tout .$

Pour tout domaine , chaque instruction étant pour tout dans .

Ordres des fonctions communes

NotationNomExemple

1 c > 1

Notation avec petit o

suffisamment grand , on écrit

0 g (x) > 0

Notation	Nom	Description	Définition formelle	Définition compacte
$ou (Notation de Vinogradov)$	Grand O ; Grand Oh ; Grand Omicron	$est borné supérieurement par$	0 \\, \\forall n\\in D\\colon \|f(n)\| \\leq k\\, g(n)" $0\,\forall n\in D\colon \|f(n)\|\leq k\,g(n) \exists k > 0 \forall n \in D : \| f (n) \| \leq k g (n)$ 0\,\forall n\in D\colon \|f(n)\|\leq k\,g(n)
	Petit O; Petit Oh; Petit O; Petit Oh		0 \\, \\exists n_0 \\, \\forall n > n_0\\colon \|f(n)\| \\leq k\\, g(n)" $0\,\exists n_{0}\,\forall n>n_{0}\colon \|f(n)\|\leq k\,g(n) \forall k > 0 \exists n_{0} \forall n > n_{0} : \| f (n) \| \leq k g (n)$ 0\,\exists n_{0}\,\forall n>n_{0}\colon \|f(n)\|\leq k\,g(n)
	Le grand Omega en théorie des nombres (Hardy–Littlewood)	$n'est pas dominé par 0\,\forall n_{0}\,\exists n>n_{0}\colon \|f(n)\|\geq k\,g(n)$	0 " $0 \underset{n \to \infty}{lim sup} \frac{\| f (n) \|}{g (n)} > 0$ 0
	Omega plus (Hardy–Littlewood)	$n'est pas dominé par 0\,\forall n_{0}\,\exists n>n_{0}\colon f(n)\geq k\,g(n)$	0 " $0 \underset{n \to \infty}{lim sup} \frac{f (n)}{g (n)} > 0$ 0
	Oméga moins (Hardy–Littlewood)	$n'est pas dominé par 0\,\forall n_{0}\,\exists n>n_{0}\colon -f(n)\geq k\,g(n)$	0 " $0 \underset{n \to \infty}{lim sup} \frac{- f (n)}{g (n)} > 0$ 0
	Oméga plus et moins	ni l' un ni l'autre n'est dominé asymptotiquement par
$(Notation de Hardy) ou (Notation de Knuth)$	Du même ordre que (Hardy) ; Grand Theta (Knuth)		0 \\, \\exists k_2>0 \\, \\forall n\\in D\\colon" $0\,\exists k_{2}>0\,\forall n\in D\colon \exists k_{1} > 0 \exists k_{2} > 0 \forall n \in D :$ 0\,\exists k_{2}>0\,\forall n\in D\colon	$et$
$comme , où est fini, ou$	équivalence asymptotique	$asymptotiquement égal à$	0 \\, \\exists n_0 \\, \\forall n > n_0\\colon \\left\| \\frac{f(n)}{g(n)} - 1 \ ight\| < \\varepsilon" $0\,\exists n_{0}\,\forall n>n_{0}\colon \left\|{\frac {f(n)}{g(n)}}-1 ight\|<\varepsilon \forall ε > 0 \exists n_{0} \forall n > n_{0} : \| \frac{f (n)}{g (n)} - 1 \| < ε$ 0\,\exists n_{0}\,\forall n>n_{0}\colon \left\|{\frac {f(n)}{g(n)}}-1 ight\|<\varepsilon (dans ce cas )
$(notation de Knuth), ou (Notation de Vinogradov)$	Le grand Omega dans la théorie de la complexité (Knuth)	$0\,\forall n\in D\colon f(n)\geq k\,g(n)$	0 " $0 inf_{n \in D} \frac{f (n)}{g (n)} > 0$ 0
$comme , où peut être fini, ou$	Petit Omega ; Petit Omega	$0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)$ (pour )

Généralisations et usages connexes

La généralisation aux fonctions à valeurs dans tout espace vectoriel normé est directe (en remplaçant les valeurs absolues par des normes), où et n'ont pas nécessairement leurs valeurs dans le même espace. Une généralisation aux fonctions à valeurs dans tout groupe topologique est également possible . Le « processus de passage à la limite » peut aussi être généralisé en introduisant une base de filtres arbitraire, c'est-à-dire des réseaux dirigés et . Cette notation permet de définir les dérivées et la différentiabilité dans des espaces assez généraux, ainsi que l'équivalence (asymptotique) des fonctions.

qui est une relation d'équivalence et une notion plus restrictive que la relation « est » ci-dessus. (Elle se réduit à si et sont des fonctions à valeurs réelles positives.) Par exemple, est, mais .

Histoire

En 1870, Paul du Bois-Reymond a défini et comme signifiant respectivement . Ces définitions n'ont pas été largement adoptées et ne sont plus utilisées aujourd'hui. La première et la troisième sont symétriques : signifie la même chose que . Landau a ensuite adopté la définition plus restrictive selon laquelle la limite de est égale à 1. $0,\quad \lim _{x o \infty }{\frac {f(x)}{\phi (x)}}=0. lim_{x \to \infty} \frac{f (x)}{ϕ (x)} = \infty, lim_{x \to \infty} \frac{f (x)}{ϕ (x)} > 0, lim_{x \to \infty} \frac{f (x)}{ϕ (x)} = 0.$

Le symbole O a été introduit pour la première fois par le théoricien des nombres Paul Bachmann en 1894, dans le deuxième volume de son ouvrage *Analytische Zahlentheorie * (« Théorie analytique des nombres »). Le théoricien des nombres Edmund Landau l'a adopté et s'est ainsi inspiré de la notation o pour introduire en 1909 ; ces deux notations sont désormais appelées symboles de Landau. Ces notations ont été utilisées en mathématiques appliquées dans les années 1950 pour l'analyse asymptotique. Le symbole o (au sens de « n'est pas petit de o ») a été introduit en 1914 par Hardy et Littlewood. Hardy et Littlewood ont également introduit en 1916 les symboles o à gauche et à droite ( désormais couramment notés o et o). Cette notation est couramment utilisée en théorie des nombres depuis les années 1950.

Hardy a introduit les symboles et défendu ceux de Bois-Reymond (ainsi que les autres symboles déjà mentionnés) dans son ouvrage de 1910 intitulé « Ordres de l'infini » , mais ne les a utilisés que dans trois articles (1910-1913). Dans ses quelque 400 autres publications et ouvrages, il a systématiquement utilisé les symboles de Landau O et o . Les symboles de Hardy ne sont plus utilisés.

Le symbole , bien qu'il ait été utilisé auparavant avec des significations différentes, a reçu sa définition moderne de Landau en 1909 et de Hardy en 1910. Sur la même page, Hardy a défini le symbole , où signifie que et sont satisfaites. Cette notation est encore utilisée en théorie analytique des nombres. Hardy a également proposé le symbole , où signifie que pour une certaine constante (cela correspond à la notation de Bois-Reymond ).

Dans les années 1930, Vinogradov a popularisé la notation et , qui signifient toutes deux . Cette notation est devenue standard en théorie analytique des nombres.

Dans les années 1970, le grand O a été popularisé en informatique par Donald Knuth , qui a proposé une notation différente pour le Ω de Hardy et a proposé une définition différente pour la notation Omega de Hardy et Littlewood.

Questions de notation

Flèches

En mathématiques, une expression telle que indique la présence d'une limite . Dans la notation grand O et les notations apparentées , il n'y a pas de limite implicite, contrairement aux notations petit o et . Une notation telle que peut être considérée comme un abus de notation .

Signe égal

Certains considèrent également qu'il s'agit d'un abus de notation , car l'utilisation du signe égal peut induire en erreur en suggérant une symétrie que cette affirmation ne possède pas. Comme le dit de Bruijn , est vrai mais ne l'est pas. Knuth qualifie de telles affirmations d'« égalités à sens unique », car si les membres pouvaient être inversés, « on pourrait déduire des choses ridicules comme à partir des identités et . Dans une autre lettre, Knuth a également souligné que

le signe d'égalité n'est pas symétrique par rapport à de telles notations [comme, dans cette notation,] les mathématiciens utilisent habituellement le signe '=' comme ils utilisent le mot 'is' en anglais : Aristote est un homme, mais un homme n'est pas nécessairement Aristote.

Pour ces raisons, certains préconisent l'utilisation de la notation ensembliste et écrivent , ce qui se lit « est un élément de » ou « appartient à l'ensemble » – en considérant comme la classe de toutes les fonctions telles que . Cependant, l'utilisation du signe égal est courante. et est plus pratique dans des expressions plus complexes de la forme

Les notations de Vinogradov et , largement utilisées en théorie des nombres ne présentent pas ce défaut, car elles indiquent plus clairement que la notation grand O désigne une inégalité plutôt qu'une égalité . Elles possèdent également une symétrie dont la notation grand O est dépourvue : signifie la même chose que . En combinatoire et en informatique, ces notations sont rarement rencontrées.

Composition

$TeX , il s'obtient simplement en tapant « O » en mode mathématique. Contrairement aux notations de Bachmann-Landau d'origine grecque, il ne nécessite aucun symbole spécial. Cependant, certains auteurs utilisent la variante calligraphique .$

Le grand O signifie à l'origine « ordre de » (« Ordnung », Bachmann 1894) et est donc une lettre latine. Ni Bachmann ni Landau ne l'ont jamais appelé « omicron ». Ce symbole a été considéré bien plus tard (1976) par Knuth comme un omicron majuscule [ en référence à sa définition du symbole oméga . Le chiffre zéro ne doit pas être utilisé.