Big O notation d'une expression

Question

Si j'ai un algorithme qui prend 4n ^ 2 + 7n se déplace à accomplir, quel est son O? O (4n ^ 2)? O (n ^ 2)?

Je sais que 7n est coupée, mais je ne sais pas si je dois garder le n ^ 2 coefficient ou non.

Merci

Answer 1

Vous devez supprimer des coefficients parce que la question demande vraiment « de l'ordre de », qui tente de le caractériser comme linéaire, exponentielle, logarithmique, etc ... C'est, lorsque n est très grand, le coefficient est de peu d'importance.

Cela explique aussi pourquoi vous laissez tomber le + 7n, parce que quand n est très grand, ce terme a une signification relativement peu à la réponse finale. Si vous êtes familier avec le calcul, on peut dire lim n> inf (4 * n ^ 2 + 7n) ~ = lim n> inf (4 * n ^ 2) ~ = lim n> inf (n ^ 2)

Vous pouvez aussi penser à ce sujet dans un sens graphique ... qui est, si vous représenter graphiquement la fonction 4n ^ 2 + 7n pour des valeurs plus grandes et plus grandes de n, un mathématicien pourrait dire « on dirait que n ^ 2 ». Certes, il devrait être un mathématicien assez libéral, que ce n'est pas une déclaration rigoureuse, mais qui est essentiellement ce que O (...) tente de transmettre.

Answer 2

Les coefficients ne sont pas pertinents dans la notation Big O, il est donc juste O (n ² ). que Wikipedia explique :

  

[...], les coefficients deviennent sans objet si l'on compare à une autre commande d'expression, comme une expression contenant un terme n ³ ou n ² .

Answer 3

Tout le monde à lire ou à écrire sur la complexité des algorithmes doivent savoir exactement ce que le Landau Symboles et < a href = « http://mathworld.wolfram.com/AsymptoticNotation.html » rel = « nofollow noreferrer »> notations asymptotiques sont, sinon ils ne comprennent pas vraiment ce qui se passe, ou simplement une approximation (et souvent trompeuse) idée.

Pour simplifier (beaucoup), laissez f et g deux fonctions f : N -> N et g : N -> N. Nous disons que f is O(g) si et seulement s'il y a une M > 0 constante telle que |f(n)| < M|g(n)|, pour tous n > M. C'est, de façon plus informelle, à partir d'une grande valeur de n, toutes les valeurs f(n) sont inférieures à un multiple de g(n) (c.-à-g croît plus rapidement que f).

Cette définition est équivalente à

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

Alors, nous allons prendre f(n) = 4n^2 + 7n et g(n) = n^2, et essayer de prouver f is O(g) (j'omettre {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

Cela implique qu'il ya une M telle que n > M ==> |f(n)| < M|g(n)|, et donc f is O(g).

Alors, techniquement, il est correct de dire 4n^2 + 7n is O(4n^2), comme il est exact de dire 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), et ainsi de suite. Mais pour avoir un sens, nous sommes intéressés à la limite inférieure. Donc, si f is O(e^n) et f is O(n^2), nous sommes plus intéressés à savoir que f is O(n^2), car cela est beaucoup plus restrictive.

TRÈS IMPORTANT Note

Quel est extremelly important lors du choix d'un algorithme est de comprendre que notations grand-O fait référence à cas asymptotiques , qui est, si l'on considère très, inimaginable d'énormes entrées , qui peuvent aller bien au-delà de la puissance de calcul disponible dans l'univers connu (par exemple, les ensembles d'entrée infini, exprimées mathématiquement par {n -> +oo}).

Pour les utilisations pratiques (c.-à-pas si d'énormes entrées), lors du choix d'un algorithme, bien sûr, vous observerez des algorithmes candidats notations grand-O , mais vous devez être en sorte que l'algorithme choisi est bien adapté (et donne de meilleurs résultats) pour votre entrée (attendu).

Enfin, il est plus difficile en général de meilleurs algorithmes performants pour comprendre et mettre en œuvre correctement. Vous devez considérer ce fait aussi bien lors du choix d'un algorithme (ie est le temps que je vais passer débogage et fixer ma mise en œuvre de cet algorithme considérablement supérieur au temps que je devrais attendre avec un autre algorithme, avec une pire notation grand-O? . Dans ce cas, vous devriez considérer le plus simple, l'algorithme moins efficace, comme la solution globale serait plus efficace).

Answer 4

Il est O (n ^ 2). Les facteurs constants « se déplacent dans le O ». Vous ne garder que le plus grand exposant puisque c'est celui qui domine. Et vous pouvez laisser des coefficients puisque lorsque l'on compare les algorithmes différents, même des coefficients très importants se traduisent par un plus petit nombre au total que d'avoir un exposant plus grand (avec n assez grand).

Answer 5

Une déclaration comme

4n² + 7n = O(n²)

signifie que pour certains c multiplicateur constant, le cn² d'expression finira par dépasser 4n² + 7n. Il est techniquement incorrect de laisser le coefficient là - O(n²) et O(4n²) signifient exactement la même chose, parce que tout c constante pour l'ex-peut être remplacé par c/4 pour ce dernier. Cependant, une telle chose est moins claire, peut-être trompeur, et certainement non standard.

Answer 6

Mathématiquement parlant, vous écririez O (4n²). Cela signifie que la fonction de la complexité de vos algorithmes se comporte comme n> 4n² vers l'infini positif.

Mais dans l'informatique / algorithme, vous n'écrire O (n²), ce qui est suffisant pour classer votre algorithme.