La différence entre le Big-O et Peu-O Notation
Quelle est la différence entre Big-O notation O(n)
et Peu-O notation o(n)
?
Vous devez vous connecter pour publier un commentaire.
Quelle est la différence entre Big-O notation O(n)
et Peu-O notation o(n)
?
Vous devez vous connecter pour publier un commentaire.
f ∈ O(g) dit, en substance
Remarque que O(g) est l'ensemble de toutes les fonctions pour lesquels cette condition est remplie.
f ∈ o(g) dit, en substance
Une fois de plus, notez que o(g) est un ensemble.
En Big-O, il est seulement nécessaire que vous en cherchez un en particulier multiplicateur k pour laquelle l'inégalité est vraie au delà d'un certain minimum x.
Dans la Petite-o, il faut qu'il y est un minimum x après laquelle l'inégalité est vraie, peu importe comment petit vous faire k, tant qu'il n'est pas négatif ou égal à zéro.
Ces deux décrivent la limite supérieure, bien que quelque peu contre-intuitivement, Peu-o est le plus fort de l'instruction. Il y a une beaucoup plus grande écart entre le taux de croissance de f et de g si f ∈ o(g) que si f ∈ O(g).
Une illustration de la disparité est-ce: 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 f est asymptotique de la croissance n'est pas plus rapide que g", alors que "f ∈ o(g) signifie que f est asymptotique de la croissance est strictement plus lent que g". C'est comme
<=
contre<
.Plus précisément, si la valeur de g(x) est une constante multiple de la valeur de f(x), alors f ∈ O(g) est vrai. C'est pourquoi vous pouvez déposer des constantes lorsque l'on travaille avec big-O notation.
Cependant, pour f ∈ o(g) pour être vrai, alors g doit inclure un plus puissance de x dans sa formule, et donc la relative séparation entre f(x) et g(x) doit en fait beaucoup plus grands que x devient plus grand.
Pour une utilisation purement exemples de mathématiques (plutôt que de se référer à des algorithmes):
Suivantes sont vraies pour Big-O, mais ne serait pas vrai si vous avez utilisé peu-o:
Suivantes sont vraies pour les petits-o:
Remarque que si f ∈ o(g), cela implique que f ∈ O(g). par exemple, x2 ∈ o(x3) c'est vrai aussi que x2 ∈ O(x3), (encore une fois, pensez à O comme
<=
et o comme<
)x ~ O(x^2)
(avec, par exemple, un=k=1)."f ∈ o(g) means that f's asymptotic growth is strictly slower than g's"
Avec cette définition,x ∈ o(2*x)
.a
il estk
que: ... ", c'est "pour chaquek
il y a una
que: ..."Big-O est à peu-o comme
≤
est à<
. Big-O est une vaste limite supérieure, tandis que la petite-o est une stricte limite supérieure.Par exemple, la fonction
f(n) = 3n
est:O(n²)
,o(n²)
, etO(n)
O(lg n)
,o(lg n)
, ouo(n)
De la même façon, le nombre
1
est:≤ 2
,< 2
, et≤ 1
≤ 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 de la limite devrait être en termes de limite supérieure au lieu de la limite normale. Par exemple,
3 + (n mod 2)
oscille entre 3 et 4 pour toujours. C'est dansO(1)
en dépit de ne pas avoir une limite normale, parce qu'il a encore unlim sup
: 4.)Je recommande la mémorisation comment le Big-O notation convertit à asymptotique des comparaisons. Les comparaisons sont faciles à retenir, mais moins flexible car vous ne pouvez pas dire des choses comme, nO(1) = P.
Je trouve que lorsque je ne peux pas conceptuellement saisir quelque chose, en pensant à pourquoi on utiliserait X est utile de comprendre X. (pour ne Pas dire que vous n'avez pas essayé, je suis juste une mise en scène.)
[des choses que vous savez]Une commune de la manière de classer les algorithmes d'exécution, et en citant le grand-Oh complexité d'un algorithme, vous pouvez obtenir une bonne estimation de ce qui est "mieux" -- selon le "petit" de la fonction dans l'O! Même dans le monde réel, O(N) est "mieux" que O(N2), d'interdiction de choses stupides comme des super-massif des constantes et la comme.[/choses que vous savez]
Disons qu'il y a un algorithme qui s'exécute en O(N). Très bon, hein? Mais disons que vous (vous personne brillante, vous) venez avec un algorithme qui s'exécute en O(N⁄loglogloglogN). YAY!!! Son plus rapide! Mais vous vous sentiriez idiot écrit que plus et plus encore, lorsque vous êtes à la rédaction de votre thèse. Donc, vous écrivez qu'une seule fois, et vous pouvez dire "Dans ce livre, j'ai prouvé que l'algorithme de 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 la façon dont beaucoup n'est pas claire, mais ils en connaissent les plus rapides. Théoriquement. 🙂