Qual è il metodo corretto per trovare l'ordine di crescita per questa funzione?

Question

2 ^ n + 6n ^ 2 + 3n

Immagino sia solo O (2 ^ n), usando il termine di ordine più alto, ma qual è l'approccio formale per provare questo?

Answer 1

Puoi provare che 2 ^ n + n ^ 2 + n = O (2 ^ n) usando i limiti all'infinito. In particolare, f (n) è O (g (n)) se lim (n- > inf.) F (n) / g (n) è finito.

lim (n->inf.) ((2^n + n^2 + n) / 2^n)

Dato che hai inf / inf, un modulo indeterminato , puoi usare regola di L'Hopital e differenziare il numeratore e il denominatore fino a ottenere qualcosa puoi lavorare con:

lim (n->inf.) ((ln(2)*2^n + 2n + 1) / (ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2) / (ln(2)*ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n) / (ln(2)*ln(2)*ln(2)*2^n))

Il limite è 1, quindi 2 ^ n + n ^ 2 + n è effettivamente O (2 ^ n) .

Answer 2

Vedi:

Compiti sulla notazione O grande - Analisi dell'algoritmo del frammento di codice?

Grande O, come si calcola / approssimazione?

Can qualcuno per favore spiega la differenza tra Big-O e Little-O Notation?

Big-O per otto anni? (non inteso per essere un insulto)