Différence entre la Notation Big-O et Little-O
Quelle est la différence entre Big-O la notation O(n) et Peu-O la notation o(n)?
3 réponses
F O O (g) dit, essentiellement
Pour , au moins un choix d'une constante k > 0, vous pouvez trouver une constante un, tels que l'inégalité 0 une.
Notez que O (g) est l'ensemble de toutes les fonctions pour lesquelles cette condition est valable.
F o o (g) dit, essentiellement
Pour tous les choix d'une constante k > 0, vous pouvez trouver une constante un, tels que l'inégalité 0 a.
Encore une Fois, notez que o(g) est un ensemble.
Dans Big-O, il suffit de trouver un multiplicateur particulier k pour lequel l'inégalité se maintient au-delà d'un minimum x .
Dans Little-o, il doit y avoir un minimum x après quoi l'inégalité tient peu importe la taille que vous faites k , tant qu'elle n'est pas négative ou nulle.
Ces deux décrivent les limites supérieures, bien que un peu contre-intuitivement, Little-o est la déclaration la plus forte. Il y a un écart beaucoup plus important entre les taux de croissance de f et G Si f o o(g) que si f ∈ O(g).
Une illustration de la disparité est la suivante: f O O (f) est vrai, mais f ∈ o (f) est faux. Par conséquent, Big-O peut être lu comme "f O O(g) signifie que la croissance asymptotique de f n'est pas plus rapide que celle de g", tandis que "f ∈ o(g) signifie que la croissance asymptotique de f est strictement plus lente que celle de 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 supprimer des constantes lorsque vous travaillez avec la notation big-O.
Cependant, pour que f o o(g) soit vrai, alors g doit inclure une puissance supérieure de x dans sa formule, et donc la séparation relative entre f(x) et g(x) doit en fait devenir plus grande à mesure que x devient plus grand.
Pour utiliser des exemples purement mathématiques (plutôt que de se référer à des algorithmes):
Ce qui suit est vrai pour Big-O, mais ce n'est pas vrai si vous avez utilisé little-o:
- x2 O O (X2)
- x2 O O (x2 + x)
- x2 O O (200 * x2)
Les valeurs suivantes sont vraies pour little-o:
- x2 o o (X3)
- x2 o o(x!)
- ln (x) o o (x)
Notez que si f o o (g), cela implique f ∈ O(g). par exemple x2 o o (x3) il est donc également vrai que x2 O O (x3), (encore une fois, pensez à O comme <= et o comme <)
Big-O est à peu-o ≤ est <. Big-O est une limite supérieure inclusive, tandis que little-o est une limite supérieure stricte.
Par exemple, la fonction f(n) = 3n est:
- dans
O(n²),o(n²), etO(n) - pas dans
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 le général idée:
(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. Il est dans O(1) malgré ne pas avoir de limite normale, car il a toujours un lim sup: 4.)
Je recommande de mémoriser comment la notation Big-O se convertit en comparaisons asymptotiques. Les comparaisons sont plus faciles à retenir, mais moins flexibles parce que vous ne pouvez pas dire des choses comme nO(1) = P.
Je trouve que quand je ne peux pas saisir conceptuellement quelque chose, penser à Pourquoi on utiliserait X est utile pour comprendre X. (Pour ne pas dire que vous n'avez pas essayé cela, je ne fais que préparer le terrain.)
[trucs que vous connaissez]une façon courante de classer les algorithmes est par runtime, et en citant la complexité big-Oh d'un algorithme, vous pouvez obtenir une assez bonne estimation de celui qui est "meilleur" - celui qui a la" plus petite " fonction dans le O! Même dans le monde réel, O (N) est "meilleur" que O (N2), sauf des choses stupides comme des constantes super-massives et autres.[/trucs que vous connaissez]
Disons qu'il y a un algorithme qui s'exécute dans 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 stupide d'écrire cela encore et encore quand vous écrivez votre thèse. Donc, vous l'écrivez une fois, et vous pouvez dire "dans cet article, j'ai prouvé que l'algorithme X, précédemment calculable dans le temps O (N), est en fait calculable dans o(n)."
Ainsi, tout le monde sait que votre algorithme est plus rapide - - - de combien n'est pas clair, mais ils savent que c'est plus rapide. Théoriquement. :)