Ordinare funzioni per complessità asintotica.
Salve a tutti, vorrei gentilmente chiedervi un' aiuto per un'esercizio che dovrò svolgere per l'esame di algoritmi.
L'esercizio è il seguente: Si ordinino le seguenti funzioni in ordine non decrescente di tasso di crescita asintotica.
\[ 2^{n/2} \]
\[ \frac{n^{2}(n+1)}{(n^{4}-1)^{1/4}} \]
\[ (n^{6}+logn)^{1/3} \]
\[ 2^{n} \]
\[ \frac{n^{2}logn-4n}{7}\]
\[ etc..\]
Considerando che le funzioni sono 12, a parte il rapporto dei limiti e l'intuito(\( 2^{n} \) è palesemente più veloce di \((n^{6}+logn)^{1/3}\)) sapreste dirmi (se esiste) un metodo più semplice e veloce per ordinare le funzioni?
Chiedo scusa anticipatamente se sto chiedendo una cosa impossibile
Grazie
L'esercizio è il seguente: Si ordinino le seguenti funzioni in ordine non decrescente di tasso di crescita asintotica.
\[ 2^{n/2} \]
\[ \frac{n^{2}(n+1)}{(n^{4}-1)^{1/4}} \]
\[ (n^{6}+logn)^{1/3} \]
\[ 2^{n} \]
\[ \frac{n^{2}logn-4n}{7}\]
\[ etc..\]
Considerando che le funzioni sono 12, a parte il rapporto dei limiti e l'intuito(\( 2^{n} \) è palesemente più veloce di \((n^{6}+logn)^{1/3}\)) sapreste dirmi (se esiste) un metodo più semplice e veloce per ordinare le funzioni?
Chiedo scusa anticipatamente se sto chiedendo una cosa impossibile
Grazie
Risposte
L'ordine di crescita asintotica è il seguente
$\log n,\ n^\alpha,\ a^n,\ n!,\ n^n$
con $\alpha>0$ e $a>1$.
$\log n,\ n^\alpha,\ a^n,\ n!,\ n^n$
con $\alpha>0$ e $a>1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo