Différence entre Big-O et Little-O Notation

Question

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

Answer 1

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 <)

Answer 2

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²) et O(n)
• pas O(lg n), o(lg n) ou o(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.

Answer 3

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. :)