Complessita' Asintotica

[M.C.D.1]

Ragazzi Ho Un Dubbio Sulla Seguente Domanda di Informatica

Quale di queste funzioni e' asintoticamente piu' grande

2n/log(n)

5n*log^3(n)+4^n * n log(n)

10n log(n)

9n^4

In Cosa Consiste?
Mi Dareste un aiutino?

[dzcosimo]

la seconda
è l'unica esponenziale

cosa vuol dire in cosa consiste?

[M.C.D.1]

Cioe' come si stabilisce se una funzione e' Asintoticamente Piu' Grande

[dzcosimo]

attraverso il metodo degli O grandi
una funzione si dice O grande di un altra se si trova classificata in una "sezione" uguale o superiore all'altra
le "sezioni"(non mi ricordo il giusto nome) se non mi sbaglio sono:
-costante
-logaritmica
-lineare
-sovralineare(nlogn)
-quadratica
-polinomiale
-esponenziale
(-fattoriale)[in genere inclusa in esponenziale]

su ognuna delle funzioni composte che hai devi applicare esaustivamente questa regola(mi pare possa bastare)
f(x)+O(f(x))=f(x) es.: logn+n^2->n^2

2n/log(n)->O(n)[asintoticamente, se non puoi semplificare con la regola che ti dicevo prima, prendi sempre la "peggiore" fra le "sezioni" a disposizione, in tal caso quadratica]

5n*log^3(n)+4^n * n log(n) qua appare un esponenziale 4^n quindi è esponenziale quindi la peggiore possibile

ecc...

queste stime sono fatte un po' ad occhio ed in base "all'esperienza"
se poi vuoi tutte le regolette ti consiglio,come ho già fatto in un altor post, di studiartele su questa dispensa

http://info.iet.unipi.it/~fondii/Algori ... ritmi.html