Big-O complessità del c ^ n + n * (log n) ^ 2 + (10 * n) ^ C

Question

Ho bisogno di ricavare la complessità O-grande di questa espressione:

  

c ^ n + n * (log (n)) ^ 2 + (10 * n) ^ c

dove c è una costante e n è una variabile.
Sono abbastanza sicuro di aver capito come derivare la complessità O-grande di ogni termine individualmente, io non so come la complessità Big-O cambia quando i termini sono combinati in questo modo.
Idee?

Qualsiasi aiuto sarebbe grande, grazie.

Answer 1

La notazione O () considera il più alto termine; Pensate a quale dominerà per molto, molto grandi valori di n.

Nel tuo caso, il termine più alto è c^n, in realtà; le altre sono essenzialmente polinomiale. Quindi, è la complessità esponenziale.

Answer 2

La risposta dipende da | c |

Se | c | <= 1 è di O (n * (log (n)) ^ 2)

Se | c | > 1 è di O (c ^ n)

Answer 3

Wikipedia è tuo amico :

  

Nel utilizzo tipico, la definizione formale di notazione O non viene utilizzato direttamente; piuttosto, la notazione O per una funzione f (x) è derivato dalle regole seguenti semplificazione:

     

  
• Se f (x) è la somma di diversi termini, quello con il tasso di crescita è mantenuta, e tutti gli altri omesso.
  
• Se f (x) è un prodotto di diversi fattori, qualsiasi costante (termine nel prodotto che non dipendono x) sono omessi.