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

ho bisogno di ricavare la complessità O-grande di questa espressione:O-grande complessità del c^n + n * (log n)^2 + (10 * n)^c

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

dove c è una costante en è una variabile.
Sono abbastanza sicuro di capire come derivare la complessità Big-O di ogni termine individualmente, semplicemente non so come la complessità di Big-O cambi quando i termini sono combinati in questo modo.
Idee?

Qualsiasi aiuto sarebbe fantastico, grazie.

fonte

2010-02-04 zebraman

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

Nel tuo caso, il termine più alto è c^n, in realtà; gli altri sono essenzialmente polinomiali. Quindi, è una complessità esponenziale.

fonte

2010-02-04 04:51:12

+1 - Sì, è giusto. Ho cancellato la mia risposta. L'ho letto come nc per qualche motivo. –

Un presupposto molto importante: C deve essere maggiore di 1. :-P –

Wikipedia is your friend:

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

Se f (x) è la somma di diversi termini, quello con il tasso di crescita è mantenuta, e tutti altri omessi.

Se f (x) è un prodotto di più fattori, tutte le costanti (termini nel prodotto che non dipendono da x) vengono omesse.

fonte

2010-02-04 04:52:06

Ho pensato che Google è :) – akif

La risposta dipende da | c |

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

IF | c | > 1 è O (c^n)

fonte

2010-02-04 05:02:26

+1 Yay per una risposta che cattura entrambi i casi di valore di C. :-P –

Non ci avevo mai pensato prima, ma qui va. Se la complessità dipende dalla grandezza di C, significa che dipende anche dalle unità utilizzate per misurare C? In caso negativo, quali unità devono essere misurate in C? – Stewart

@Stewart Non penso che c possa essere espresso in alcune unità. Se potesse allora l'unità dell'espressione dipenderebbe da n e (10 * n)^c non avrebbe molto senso. –

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

risposta

Problemi correlati