[Algoritmi] Confronto asintotico di due funzioni.
Salve a tutti
Date le due funzioni $f(n) = 2^n, g(n)=2^(n/4)$ devo determinare, utilizzando le definizioni, se $f(n) =O(g(n)), f(n) = Ω(g(n))$ oppure $f(n) = Θ(g(n))$. Vi posto il procedimento fatto, ho qualche dubbio sul valore di $n_0$ e $c$ che derivano dalle definizioni.
$f(n)=O(g(n))$
$2^n<=c2^(n/4)$
$n<=log_2c + n/4$
$3/4n<=log_2c$ trovo sempre un valore di n che è più grande della costante quindi non è O(g(n)).
$f(n) = Ω(g(n))$
$c2^(n/4)<=2^n$
$4/3log_2c<=n$ è valido per ogni $n_0>4/3log_2c$ e $c>=1$ quindi è $f(n) = Ω(g(n))$. Tale soluzione è corretta o devo fissare un valore di $c$ ? C'è qualche imprecisione?
Date le due funzioni $f(n) = 2^n, g(n)=2^(n/4)$ devo determinare, utilizzando le definizioni, se $f(n) =O(g(n)), f(n) = Ω(g(n))$ oppure $f(n) = Θ(g(n))$. Vi posto il procedimento fatto, ho qualche dubbio sul valore di $n_0$ e $c$ che derivano dalle definizioni.
$f(n)=O(g(n))$
$2^n<=c2^(n/4)$
$n<=log_2c + n/4$
$3/4n<=log_2c$ trovo sempre un valore di n che è più grande della costante quindi non è O(g(n)).
$f(n) = Ω(g(n))$
$c2^(n/4)<=2^n$
$4/3log_2c<=n$ è valido per ogni $n_0>4/3log_2c$ e $c>=1$ quindi è $f(n) = Ω(g(n))$. Tale soluzione è corretta o devo fissare un valore di $c$ ? C'è qualche imprecisione?
Risposte
Riuppo.
E' sufficiente dimostrare che $c$ ed $n_0$ esistano, non è necessario trovare dei valori particolari. La dimostrazione andrebbe scritta però meglio, in modo un po' più preciso e formale.
Grazie per la risposta. Come potrei fare?
Io avevo fissato c=1 e trovato di conseguenza $n_o$.
Io avevo fissato c=1 e trovato di conseguenza $n_o$.
"mosca9":
Salve a tutti
Date le due funzioni $f(n) = 2^n, g(n)=2^(n/4)$ devo determinare, utilizzando le definizioni, se $f(n) =O(g(n)), f(n) = Ω(g(n))$ oppure $f(n) = Θ(g(n))$. Vi posto il procedimento fatto, ho qualche dubbio sul valore di $n_0$ e $c$ che derivano dalle definizioni.
$f(n)=O(g(n))$
$2^n<=c2^(n/4)$
$n<=log_2c + n/4$
$3/4n<=log_2c$ trovo sempre un valore di n che è più grande della costante quindi non è O(g(n)).
$f(n) = Ω(g(n))$
$c2^(n/4)<=2^n$
$4/3log_2c<=n$ è valido per ogni $n_0>4/3log_2c$ e $c>=1$ quindi è $f(n) = Ω(g(n))$. Tale soluzione è corretta o devo fissare un valore di $c$ ? C'è qualche imprecisione?
Scusate una domanda stupida: ma $2^n<=c2^(n/4)$ come diventa $n<=log_2c + n/4$ ?
Grazie.
"smartmouse":
Scusate una domanda stupida: ma $2^n<=c2^(n/4)$ come diventa $n<=log_2c + n/4$ ?
Grazie.
Fai il logaritmo in base due di entrambi i membri.
Grazie mille, ora è molto più chiaro il primo post 
Verifico la $f(n)=O(g(n))$ e ottengo:
$2^n<=c2^(n/4)$
$n<=log_2c + n/4$
$n<=4/3log_2c$
ponendo ad esempio $n = 1$ e $c = 1$ già ottengo un controesempio per dire che non è $O(g(n))$.
Procedo con la verifica di $f(n) = Ω(g(n))$ e ottengo:
$2^n>=c2^(n/4)$
$n>=4/3log_2c$
che è valida per ogni $n >= 4/3log_2c$ con $c >= 1$ e quindi è $Ω(g(n))$.
Ne segue infine che $f(n)$ non è $Θ(g(n))$.
Giusto? Perché dite che non va bene? Come si svolge correttamente questo esercizio?
Verifico la $f(n)=O(g(n))$ e ottengo:
$2^n<=c2^(n/4)$
$n<=log_2c + n/4$
$n<=4/3log_2c$
ponendo ad esempio $n = 1$ e $c = 1$ già ottengo un controesempio per dire che non è $O(g(n))$.
Procedo con la verifica di $f(n) = Ω(g(n))$ e ottengo:
$2^n>=c2^(n/4)$
$n>=4/3log_2c$
che è valida per ogni $n >= 4/3log_2c$ con $c >= 1$ e quindi è $Ω(g(n))$.
Ne segue infine che $f(n)$ non è $Θ(g(n))$.
Giusto? Perché dite che non va bene? Come si svolge correttamente questo esercizio?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo