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

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

f ∈ O (g) dit, essentiellement

Pour au moins un choix d'une constante k > 0, vous pouvez trouver une constante a telle que l'inégalité 0 <= f (x) <= kg (x) soit 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) dit, essentiellement

Pour chaque choix d'une constante k > 0, vous pouvez trouver une constante a telle que l'inégalité 0 <= f (x) <kg (x) soit valable pour tout x> 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 lequel l'inégalité tient, peu importe la taille de k , tant qu'elle n'est pas négative ou nulle.

Ces deux termes décrivent les limites supérieures, bien que quelque peu contre-intuitif, Little-o est la déclaration la plus forte. Il existe un écart beaucoup plus important entre les taux de croissance de 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 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 un multiple constant de la valeur de f (x), alors f ∈ O (g) est vraie. C'est pourquoi vous pouvez supprimer des constantes lorsque vous travaillez avec la notation big-O.

Cependant, pour que f ∈ o (g) soit vrai, alors g doit inclure une puissance plus élevée de x dans sa formule, et donc la séparation relative entre f (x) et g (x) doit en fait devenir plus grande au fur et à mesure que x devient plus grand.

Pour utiliser des exemples purement mathématiques (plutôt que de faire référence à des algorithmes):

Ce qui suit est vrai pour Big-O, mais ne serait pas vrai si vous avez utilisé little-o:

• x² ∈ O (x²)
• x² ∈ O (x² + x)
• x² ∈ O (200 * x²)

Ce qui suit est vrai pour little-o:

• x² ∈ o (x³)
• x² ∈ o (x!)
• ln (x) ∈ o (x)

Notez que si f ∈ o (g), cela implique f ∈ O (g). par exemple x² ∈ o (x³) donc il est également vrai que x² ∈ O (x³), (encore une fois, pensez à O as <=et o as <)

Big-O est à peu o comme ≤c'est <. Big-O est une borne supérieure inclusive, tandis que little-o est une borne supérieure stricte.

Par exemple, la fonction f(n) = 3nest:

• dans O(n²), o(n²)etO(n)
• pas O(lg n), o(lg n)ouo(n)

De façon analogue, le nombre 1est:

• ≤ 2,, < 2et≤ 1
• non ≤ 0, < 0ou< 1

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

(Remarque: le tableau est un bon guide mais sa définition de 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 en O(1)dépit de ne pas avoir de limite normale, car il a toujours a lim sup: 4.)

Je recommande de mémoriser la conversion de la notation Big-O en comparaisons asymptotiques. Les comparaisons sont plus faciles à retenir, mais moins flexibles car vous ne pouvez pas dire des choses comme n ^{O (1)} = P.

Je trouve que lorsque je ne peux pas saisir quelque chose sur le plan conceptuel, il est utile de comprendre pourquoi on utiliserait X. (Pour ne pas dire que vous n'avez pas essayé cela, je prépare le terrain.)

[trucs que vous connaissez] Une façon courante de classer les algorithmes est par le runtime, et en citant la complexité big-Oh d'un algorithme, vous pouvez obtenir une assez bonne estimation de celle qui est "meilleure" - celle qui a la fonction "la plus petite" dans le O! Même dans le monde réel, O (N) est "meilleur" que O (N²), sauf les choses idiotes comme les constantes super-massives et autres. [/ Stuff you know]

Disons qu'il y a un algorithme qui s'exécute en O (N). Assez bien, hein? Mais disons que vous (vous, personne brillante, vous) trouvez un algorithme qui s'exécute en O ( ^N ⁄ _{loglogloglogN} ). YAY! C'est plus rapide! Mais vous vous sentiriez idiot d'écrire cela encore et encore lorsque vous rédigez votre thèse. Vous l'écrivez donc une fois, et vous pouvez dire "Dans cet article, j'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 --- de combien n'est pas clair, mais ils le savent plus vite. Théoriquement. :)