∑
MathTCG
#076 / 100•Analysis & Infinity•MathTCG #276 / 500•★Commune•∫Analyse•Concept

Grand O de Landau

Période historique : 1894

Notation de domination asymptotique universelle en analyse et en complexité algorithmique.

Contenu & Formulation mathématique

Définition rigoureuse
Notation mesurant l'ordre de grandeur maximal d'une fonction par rapport à une fonction de référence.
Notation usuelle & Exemples
T(n) = O(n \log n)
f(x)=O(g(x))  ⟺  ∃M>0,  ∃V,  ∀x∈V,  ∣f(x)∣≤M∣g(x)∣f(x) = O(g(x)) \iff \exists M > 0,\; \exists V,\; \forall x \in V,\; |f(x)| \le M |g(x)|

Genèse & Portée historique

La relation f(x) = O(g(x)) signifie que la valeur absolue de f est majorée par une constante positive fois celle de g au voisinage d'un point. En informatique, elle quantifie le temps de calcul ou l'espace mémoire d'un algorithme dans le pire des cas.

Adoptée par Donald Knuth dans les années 1970 pour formaliser la complexité des algorithmes, la notation Grand O est aujourd'hui parlée par tous les programmeurs de la planète.

« Fixer la borne supérieure infranchissable du coût temporel ou de l'erreur de calcul. »

Filiations & Relations conceptuelles (0)

Cette notice constitue un axiome autonome sans relations directes enregistrées dans le recueil.

Objet de collection MathTCG

#276
★Commune
∫

Grand O de Landau

Analyse•CONCEPT

Notation mesurant l'ordre de grandeur maximal d'une fonction par rapport à une fonction de référence.

f(x)=O(g(x))  ⟺  ∃M>0,  ∃V,  ∀x∈V,  ∣f(x)∣≤M∣g(x)∣f(x) = O(g(x)) \iff \exists M > 0,\; \exists V,\; \forall x \in V,\; |f(x)| \le M |g(x)|
1894

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Analysis & Infinity.

Extension : Analysis & Infinity (#076 / 100)
Numéro global MathTCG : MathTCG #276 / 500
Rareté officielle : Commune (★)
Domaine théorique : Analyse
Identifiant pérenne : grand-o-de-landau
Consulter mon classeurExplorer tout le recueil