s
19 708 Pages

Big O
Exemple de notation grand-O: f (x) ∈ O (g (x)), il y a c> 0 et une valeur x0 de telle sorte que la droite de x0 nous avons f (x) < c g(x)

La notation mathématique Big O Il est utilisé pour décrire la comportement asymptotique tout fonctions. Son objectif est de caractériser le comportement d'une fonction des sujets élevés dans une simple mais rigoureuse, afin de pouvoir comparer le comportement de plusieurs fonctions parmi eux. Plus précisément, il est utilisé pour décrire une limite asymptotique supérieure de l'amplitude d'une fonction par rapport à l'autre, qui a généralement une forme plus simple. Il dispose de deux principaux domaines d'application: en mathématiques, Il est généralement utilisé pour caractériser le reste de la troncature d'un série infini, en particulier d'un asymptotique, tandis que dans informatique Il est utile dans l'analyse des complexité de algorithmes.

utilisation informelle, la notation OU Il est couramment utilisé pour décrire une limite asymptotique serré, mais les limites sont plus strictes asymptotique formellement et correctement noté par lettre Θ (grand Theta), comme décrit ci-dessous.

histoire

Cette notation a été introduite pour la première fois depuis théorie des nombres allemand Paul Bachmann en 1894, dans le second volume du livre analytique Zahlentheorie ( « Théorie analytique des nombres »), le premier volume (qui contenait encore la notation Big O) est sorti en 1892. La notation est devenue populaire grâce au travail d'une autre théorie des nombres allemands, Edmund Landau, raison pour laquelle aujourd'hui, il est parfois appelé symbole de Landau. Le grand-O, signifiant « ordre », était à l'origine un omicron capital; Il est maintenant aussi utilisé une lettre majuscule OU, mais jamais le chiffre zéro.

L'utilisation

Il y a deux utilisations pour cette notation, qui sont formellement proches, mais bien différentes: asymptotes interminable et asymptotes infinitésimale. Cette distinction est une application uniquement et non de principe. Cependant, la définition formelle de « grand-O » est le même dans les deux cas, la seule différence de la valeur à laquelle la limite de la fonction tend à laquelle elle a l'intention d'appliquer la « grand-O. »

infini comportement asymptotique

La notation Big O est utile dans l'analyse de l'efficacité des algorithmes. Par exemple, supposons que vous avez fait le temps (ou le nombre d'étapes) qui sont nécessaires pour compléter un problème de taille n les deux T(n) = 4n² - 2n + 2.

Pour les grandes valeurs de n, le terme n² devenue prédominante que l'autre, qui ne peut être considéré; par exemple, pour n égale à 500, le terme 4n² sera égale à 1000 fois le terme 2n, et ignorer ce dernier, dans la plupart des cas, approximation tolérable.

De plus, même les coefficients devenu sans objet si l'on compare l'expression ci-dessus à un ordre supérieur, comme l'un contenant un terme n³ ou 2n. si T(n) = 1000000n² si U(n) = n³, U(n) Sera toujours supérieure à T(n) à n supérieur à un million (T(1000000) = = 1.000.000³ U(1000000)).

La notation grand O peut exprimer ce concept: écrire

et nous dirons que l'algorithme a une complexité temporelle ordre de n2.

Big O et infinitésimale

La notation grand-O peut également être utilisé pour décrire le terme d'erreur dans une approximation d'une fonction. Par exemple,

exprime le fait que la différence Il est plus petit valeur absolue le multipliée par une constante positive quand x Il est suffisamment proche de 0.

définition formelle

supposer et sont deux fonctions définies sur certains sous-ensemble de reals. Disons

pour

ssi

0 \; \ forall x> x_ {0}: | f (x) | \ leq c | g (x) |} « />.

La notation peut également être utilisé pour décrire le comportement des dans 'rond d'un nombre réel : Dites

pour

ssi

0 \; \ exists c> 0: | f (x) | \ leq c | g (x) |} « /> pour .

si est rien aux valeurs assez proche de , ces deux définitions peuvent être unifiée à l'aide du limite supérieure:

pour

ssi

.
Big O
Théorie de notation OU-grand: fa Il est de l'ordre de g (fa(x) ∈ OU(g(x))) Si et seulement s'il existe un nombre réel positif M et un nombre réel x0 de telle sorte que pour tous X, |fa(x) | <= M ⋅ |g(x) | Quand x < x0

En mathématiques, le comportement asymptotique pour et à Ils sont tous deux considérés. en théorie de la complexité de calcul, Ils ne sont utilisés que celles qui tendent à l'infini; , Ils sont également considérés que des fonctions toujours positives, ne peut donc être omis la valeur absolue.

exemple

Considérons les deux polynômes

puis

démonstration:

Nous montrons que pour chaque 1 « /> est une constante qui déterminera plus tard.

supposer 1 « />. de inégalité du triangle vous que

(La dernière étape, le remplacement est justifiée par le fait que 1> 0 « />)

Nous observons que pour 1 « /> appliquer l'inégalité et . De ceux-ci, nous obtenons que

et alors

prise nous obtenons l'idée.

Problèmes de notation

La déclaration " Il est de l'ordre de « Est souvent écrit »« . Voici un abus de notation: Nous ne sommes pas vraiment affirmions l'égalité des deux fonctions, ne représente pas une seule fonction, mais une classe des fonctions. Il serait plus correct d'écrire "» Comme on le voit ci-dessus.

Parfois aussi il écrit "« Pour indiquer que . Bien que ce soit un abus de notation: celle indiquée dans la première expression est pas une véritable égalité, puisqu'il n'est pas symétrique. Par exemple, avec cette notation, nous avons

mais

que la fonction il est mais pas pour qui tend vers l'infini.

Dans une utilisation plus complexe, Il peut apparaître à différents endroits d'une équation, même plusieurs fois dans chaque membre. Par exemple, les déclarations suivantes sont remplies

La signification de ces déclarations est la suivante: pour toute fonction qui satisfait chacun des membres de O plus grand de la gauche, il y a une fonction qui satisfait chacun des Big O dans la droite, de sorte que la substitution de ces fonctions dans l'équation fait membres égaux. Par exemple, le troisième moyen de l'équation: « Pour chaque fonction fa(n) ∈O (1) « il y a une fonction g(n) ∈O (etn) Tel que nfa(n)=g(n). « En termes d'ensembles, le sens est que la classe des fonctions représentées par le côté gauche est un sous-ensemble de la classe des fonctions représentées par le côté droit.

Les commandes des fonctions parmi les plus courantes

Voici une liste des classes de fonctions couramment rencontrées dans l'analyse des algorithmes. Tous ceux-ci devraient être pris en considération pour Elle tend vers l'infini. Les fonctions sont répertoriées par l'ampleur croissante (en termes de ensembliste, chaque classe est une des fonctions énumérées surensemble précédent). Dans ce qui suit, Il indique une constante arbitraire.

notation nom exemple
stable Déterminer si un nombre est pair ou impair
logarithmique itérée L'algorithme de recherche de Hopcroft et Ullman sur un ensemble disjoint (un type de structure de données)
logarithmique Recherchez un élément dans une liste ordonnée en utilisant l'algorithme recherche binaire
polilogaritmica décider si Le premier est par Test de primalité AKS
linéaire Recherchez un élément dans une liste non ordonnée
loglinear Liste des commandes par sorte tas
quadratique Liste des commandes par sorte d'insertion
polynôme Trouver le chemin le plus court sur un graphique et pesé par l 'Floyd algorithme Warshall
exponentiel, parfois appelé géométrique Trouver la solution exacte Problème commis voyageur (En supposant que P ≠ NP)
factoriel tout problème NP-complet en utilisant un algorithme qui recherche la solution avec un Procédé de force brute

Articles connexes

  • estimé asymptotique