Notation grand O

---

La notation grand O (avec la lettre majuscule O, et non pas zéro), aussi appelée symbole de Landau, est un symbole utilisé en théorie de la complexité, en informatique, et en mathématiques pour décrire le comportement asymptotique des fonctions. Fondamentalement, elle indique avec quelle rapidité une fonction « augmente » ou « diminue ».

Le symbole de Landau porte le nom du mathématicien allemand spécialisé en théorie des nombres Edmund Landau qui utilisa cette notation introduite primitivement par Bachmann. La lettre O est utilisée parce que la course de la « croissance » d'une fonction est aussi appelée l'ordre.

Par exemple, en analysant un algorithme, nous pourrions trouver que le temps (ou le nombre d'étapes) qu'il prend pour résoudre un problème de taille n est donné par T(n) = 4 n² - 2 n + 2. Si nous ignorons les constantes (ce qui a un sens parce qu'elles dépendent du matériel particulier sur lequel le programme s'exécute) et les termes qui croissent le plus lentement, nous pourrions dire « T(n) croît de l'ordre de n² » et nous écririons:T(n) = O(n²). En mathématiques, il est souvent important de garder un œil sur le terme d'erreur d'une approximation. Par exemple, nous pouvons écrire :

$e^x=1+x+\; \backslash frac\{1\}\{2\}\; x^2+O(x^3)\backslash \; \{\backslash rm\; quand\}\backslash \; x\backslash rightarrow\; 0$

pour exprimer le fait que l'erreur est plus petite en valeur absolue qu'une constante de fois x³ quand x est assez proche de 0.

Pour la définition formelle, supposons que f et g soient deux fonctions définies sur une partie de l'ensemble des nombres réels. Nous écrivons :

f(x) = O(g(x))

(ou f(x) = O(g(x)) quand x → ∞ pour être plus précis) si et seulement s’il existe des constantes N et C telles que

pour tout x>N, |f(x)| ≤ C |g(x)|.

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

Si a est un nombre réel, nous écrivons

f(x) = O(g(x))     quand x → a

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

pour tout x tel que |x-a| < d, |f(x)| ≤ C |g(x)|.

La première définition est la seule que nous utilisons en informatique (où typiquement seules les fonctions positives à variable entière n sont considérées; les valeurs absolues peuvent être alors ignorées), tandis que les deux définitions peuvent être utilisées en mathématiques.

Applications analytique

---

Voici une liste de catégories de fonctions qui sont couramment rencontrées dans les analyses d'algorithmes. Les fonctions de croissance la plus lente sont listées en premier. c est une constante arbitraire.

-

notation

complexité

-

O(1)

constante

-

O(log(n))

logarithmique

-

O(n log(n))

parfois appelée « linéarithmique »

-

O((log(n))c)

polylogarithmique

-

O(n)

linéaire

-

O(n2)

quadratique

-

O(nc)

polynomiale, parfois « géometrique »

-

O(cn)

exponentielle

-

O(n!)

factorielle

Notons que O(n^c) et O(cⁿ) sont très différents. Le dernier grandit beaucoup plus rapidement, pour n'importe quelle constante c>1. Une fonction qui grandit plus rapidement que n'importe quelle puissance de n est appelée super-polynomiale. Une qui grandit plus lentement qu'une fonction exponentielle de la forme c ⁿ est appelée sous-exponentielle. Un algorithme peut demander un temps qui est à la fois super-polynomial et sous-exponentiel; les exemples de ceci incluent les algorithmes connus comme étant les plus rapides pour la factorisation d'un nombre entier.

• Remarquons aussi, que O(log n) est exactement identique à O(log(n^c)). Les logarithmes diffèrent seulement d'un facteur constant, et la notation grand O ne tient pas compte de cela. 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 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

---

Nous pouvons signaler ici que le nombre d'opérandes dans la somme doit être constant et peut ne pas dépendre de n.

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

L'écriture:	f(n,m) = n2 + m3 + O(n+m)
correspond à la proposition:	∃C ∃N ∀n,m>N : f(n,m)≤n2+m3+C(n+m)

Évidemment, cette notation abuse du symbole d'égalité, puisque elle viole l'axiome d'égalité: « des choses égales à la même chose sont égales entre elles ». 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.

Un autre problème est que la variable par rapport à laquelle le comportement asymptotique est examiné n'est pas clairement indiquée. Une affirmation telle que f(x,y) = O (g(x,y)) exige quelque explication supplémentaire pour préciser ce que cela signifie. Cette difficulté se produit rarement dans la pratique.

Analyse réelle | Landau-Symbole Landau notation ランダウの記号