Différence entre Big-O et Little-O Notation
-
21-09-2019 - |
Question
Quelle est la différence entre Big-O notation O(n)
et Little-O notation o(n)
?
La solution
f ∈ O (g) indique, essentiellement
au moins un choix d'une constante k > 0, vous pouvez trouver une constante a de telle sorte que l'inégalité 0 <= f (x) <= kg (x) est valable pour tout x> a.
Notez que O (g) est l'ensemble de toutes les fonctions pour lesquelles cette condition est vérifiée.
f ∈ O (g) indique, essentiellement
tous choix d'une constante k > 0, vous pouvez trouver une constante a de telle sorte que l'inégalité 0 <= f (x )
a.
Encore une fois, notez que o (g) est un ensemble.
Dans Big-O, il est seulement nécessaire que vous trouviez un multiplicateur particulier k pour lesquels l'inégalité est au-delà de certains au moins x .
Petit-o, il faut que il y a un minimum x , après quoi l'inégalité est peu importe la taille que vous faites k , tant que ce n'est pas négatif ou nul.
Ces deux décrivent des limites supérieures, bien que quelque peu contre-intuitive, Little-o est la déclaration plus forte. Il existe un décalage beaucoup plus important entre les taux de croissance des f et g si f ∈ O (g) que si f ∈ O (g).
Une illustration de la disparité est la suivante: f ∈ O (f) est vrai, mais f ∈ O (f) est faux. Par conséquent, Big-O peut être lu comme « f ∈ O (g) signifie que la croissance asymptotique de f est pas plus rapide que g de », alors que « f ∈ o (g) signifie que la croissance asymptotique de f est strictement plus lent que les g ». Il est comme <=
par rapport <
.
Plus précisément, si la valeur de g (x) est un multiple constant de la valeur de f (x), alors f ∈ O (g) est vrai. Ceci est la raison pour laquelle vous pouvez déposer des constantes lorsque vous travaillez avec la notation grand-O.
Cependant, pour f ∈ O (g) à être vrai, alors g doit comporter une plus grande puissance de x dans sa formule, et ainsi la séparation relative entre f (x) et g (x ) doit effectivement obtenir plus que x devient plus grande.
Pour utiliser purement exemples de mathématiques (plutôt que de se référer à des algorithmes):
Ce qui suit sont vraies pour Big-O, mais ne serait pas vrai si vous avez utilisé peu o:
- x² ∈ O (x²)
- x² ∈ O (x² + x)
- x² ∈ O (200 * x²)
Les éléments suivants sont vrai pour peu o:
- x² ∈ o (X³)
- x² ∈ o (x!)
- ln (x) ∈ o (x)
Notez que si f ∈ O (g), ce qui implique f ∈ O (g). par exemple. x² ∈ o (X³) de sorte qu'il est également vrai que x² ∈ O (X³), (encore une fois, pense que O et o <=
comme <
)
Autres conseils
Big-O est à peu o comme ≤
est de <
. Big-O est une limite supérieure y compris, tandis que le petit-o est une limite supérieure stricte.
Par exemple, la fonction f(n) = 3n
est:
- dans
O(n²)
,o(n²)
etO(n)
- pas
O(lg n)
,o(lg n)
ouo(n)
De manière analogue, le nombre 1
est:
-
≤ 2
,< 2
et≤ 1
- pas
≤ 0
,< 0
ou< 1
Voici un tableau montrant l'idée générale:
(Note: le tableau est un bon guide, mais sa définition limite devrait être en termes de < . / a> au lieu de la limite normale, par exemple, 3 + (n mod 2)
oscille entre 3 et 4 pour toujours il est en O(1)
malgré ne pas avoir une limite normale, car il a encore lim sup
:.. 4)
Je recommande la mémorisation de la façon dont la notation Big-O convertit les comparaisons asymptotique. Les comparaisons sont plus faciles à retenir, mais moins flexible parce que vous ne pouvez pas dire des choses comme n O (1) = P.
Je trouve que quand je ne peux pas saisir quelque chose sur le plan conceptuel, penser à pourquoi on utiliserait X est utile de comprendre X. (Pour ne pas dire que vous ne l'avez pas essayé, je suis le réglage de la scène.)
[des choses que vous connaissez] Une façon courante de classer les algorithmes est en exécution et en citant la complexité grand-Oh d'un algorithme, vous pouvez obtenir une assez bonne estimation dont on est « meilleure » - selon a " la plus petite » fonction dans le O! Même dans le monde réel, O (N) est « meilleure » que O (N²), sauf les choses stupides comme des constantes super-massives et autres. [/ Choses que vous connaissez]
Disons qu'il ya un algorithme qui fonctionne dans O (N). Très bon, hein? Mais disons que vous (vous personne brillante, vous) venez avec un algorithme qui fonctionne en O ( N / loglogloglogN ). YAY! C'est plus rapide! Mais vous sentez l'écriture stupide qui encore et encore quand vous écrivez votre thèse. Donc, vous écrivez une fois, et vous pouvez dire « Dans cet article, je l'ai prouvé que l'algorithme X, précédemment calculable en temps O (N), est en fait calculable en o (n). »
Ainsi, tout le monde sait que votre algorithme est plus rapide --- par combien est peu claire, mais ils savent le plus rapide. Théoriquement. :)