complexité Big-O de c ^ n + n * (log n) ^ 2 + (10 * n) ^ c
-
25-09-2019 - |
Question
Je dois tirer la complexité Big-O de cette expression:
c ^ n + n * (log (n)) ^ 2 + (10 * n) ^ c
où c est une constante et n est une variable.
Je suis sûr que je comprends comment tirer la complexité Big-O de chaque terme individuellement, je ne sais pas comment la complexité Big-O change lorsque les termes sont combinés comme celui-ci.
Idées?
Toute aide serait génial, merci.
La solution
La notation O () considère que le terme le plus élevé; penser que l'on va dominer pour très, très grandes valeurs de n
.
Dans votre cas, le plus long terme est c^n
, en fait; les autres sont essentiellement polynomiale. Ainsi, il est la complexité exponentielle.
Autres conseils
La réponse dépend | c |
Si | c | <= 1, il est O (n * (log (n)) ^ 2)
IF | c | > 1, il est O (C ^ n)
Dans l'usage typique, la définition formelle de la notation O n'est pas utilisé directement; plutôt, la notation O pour une fonction f (x) est dérivé par les règles de simplification suivante:
- Si f (x) est une somme de plusieurs termes, celui qui a le plus fort taux de croissance est maintenue, et tous les autres omis.
- Si f (x) est un produit de plusieurs facteurs, les constantes (termes du produit qui ne dépendent pas de x) sont omis.