complexité Big-O de c ^ n + n * (log n) ^ 2 + (10 * n) ^ c

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.

Answer 1

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.

Answer 2

La réponse dépend | c |

Si | c | <= 1, il est O (n * (log (n)) ^ 2)

IF | c | > 1, il est O (C ^ n)

Answer 3

Wikipédia est votre ami :

  

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.