Différence entre la notation Big-O et Little-O

Question

Quelle est la différence entre la notation Big-O ( O(n) ) et la notation Little-O ( o(n) )?

Answer 1

f ∈ O(g) dit, en substance

Pour au moins un choix d'une constante k > 0, vous pouvez trouver une constante a telle que l'inégalité f(x) < k g(x) vaut pour tout x > une.

Notez que O(g) est l'ensemble de toutes les fonctions pour lesquels cette condition est remplie.

f ∈ o(g) dit, en substance

Pour chaque choix d'une constante k > 0, vous pouvez trouver une constante a telle que l'inégalité f(x) < k g(x) vaut pour tout x > une.

Une fois de plus, notez que o(g) est un ensemble.

En Big-O, il est seulement nécessaire que vous trouver un multiplicateur de k pour laquelle l'inégalité est vraie au delà d'un certain minimum de x.

Dans la Petite-o, il faut qu'il y est un minimum de x après laquelle l'inégalité est vraie, peu importe comment petit vous rendre 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 de notation.

Cependant, pour f ∈ o(g) pour être vrai, alors g doit inclure plus de 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):

Les conditions suivantes sont remplies pour Big-O, mais ne serait pas vrai si vous avez utilisé peu-o:

• x^2 ∈ O(x^2)
• x^2 ∈ O(x^2 + x)
• x^2 ∈ O(200 * x^2)

Les conditions suivantes sont remplies pour les petits-o:

• x^2 ∈ o(x^3)
• x^2 ∈ o(x!)
• ln(x) ∈ o(x)

Remarque que si f ∈ o(g), cela implique que f ∈ O(g). par exemple, x^2 ∈ o(x^3) il est vrai aussi que x^2 ∈ O(x^3), (encore une fois, pensez à O <= et o <)

Answer 2

Big-O est à Peu-o <= est <. Big-O est une vaste limite supérieure, et Peu-o est une stricte limite supérieure.

Par exemple, une fonction qui croît linéairement:

• Est - O(n^2), o(n^2) et O(n)
• N'est pas o(n), O(lg n) ou o(lg n)

De la même façon, le nombre 1:

• Est - <= 2, < 2 et <= 1
• N'est pas < 1, <= 0 ou < 0

Voici un tableau montrant l'idée générale:

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 n^O(1) = P.

Answer 3

Je trouve que lorsque je ne peux pas conceptuellement saisir quelque chose, de penser à 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.)

[trucs 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(N^2), sauf les 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. :)