La notation du grand oh dit que tout g (n) est un élément c.f (n), O (g (n)) pour une constante c.Constante de complexité asymptotique, pourquoi la constante?
Je me suis toujours demandé et n'ai jamais vraiment compris pourquoi nous avons besoin de multiplier cette constante arbitraire avec la fonction de délimitation f (n) pour obtenir nos limites?
Comment décider du nombre de cette constante?
La constante elle-même ne caractérise pas le comportement limitant de f (n) par rapport à g (n).
Il est utilisé pour la définition mathématique, qui impose l'existence d'une constante M telle que
Si existe une telle constante, vous pouvez alors dire que f (x) est un O (g (x)), et c'est la notation habituelle lors de l'analyse des algorithmes, vous ne vous souciez pas de savoir quelle est la constante mais juste la complexité des opérations elle-même. La constante est capable de corriger cette déséquilibre en s'assurant que M | g (x) | est une limite supérieure de f (x). Comment trouver cette constante dépend de f (x) et g (x) et c'est le point mathématique qui doit être prouvé pour s'assurer que f (x) a ag (x) big-o donc il n'y a pas de général règle. Regardez l'exemple this.
Tenir compte fonction
f(n) = 4 * n
-t-il pas logique d'appeler cette fonction O(n) car il pousse « aussi vite » que g(n) = n. Mais sans constante dans la définition de O vous ne pouvez pas trouver n0 comme cela pour tous n > n0, f(n) <= n. Voilà pourquoi vous avez besoin constant, et même de la condition,
4 * n <= c * n for all n > n0
vous pouvez obtenir n0 == 0, c == 4.