[Algoritmi] Equazione di ricorrenza
Salve a tutti, volevo chiedere consiglio su come procedere in questo esercizio:
considerare la relazione di ricorrenza:
$T(n) = {(c rarr n <= 9),(3T(n/9)+n^alpha rarr n > 9):}$
dire per quali valori di $alpha$ è possibile che risulti:
$T(n) = Theta(log(n))$
$T(n) = Theta(sqrt(n))$
$T(n) = Theta(sqrt(n)log(n))$
$T(n) = Theta(n)$
Grazie
considerare la relazione di ricorrenza:
$T(n) = {(c rarr n <= 9),(3T(n/9)+n^alpha rarr n > 9):}$
dire per quali valori di $alpha$ è possibile che risulti:
$T(n) = Theta(log(n))$
$T(n) = Theta(sqrt(n))$
$T(n) = Theta(sqrt(n)log(n))$
$T(n) = Theta(n)$
Grazie
Risposte
Ciao,
passa per il Master Theorem.
passa per il Master Theorem.
"hamming_burst":
Ciao,
passa per il Master Theorem.
Grazie del consiglio!
ho provato ad applicare il Teorema master al secondo caso, dove richiede $T(n) = Theta(sqrt(n))$
e mi è venuto così:
per $alpha = 1/2 rArr f(n) = sqrt(n)$
dato che il primo punto del teorema master richiede che $ f(n) = O(n^(log_b a))$
quindi $f(n) = O(n^(log_9 3) ) = O(sqrt(n))$ quindi per $alpha = 1/2 rArr T(n) = Theta(sqrt(n))$
Secondo voi può andare??
Poi stavo provando a ragionare su $T(n) = Theta(sqrt(n)logn)$
sono quasi sicuro che devo applicare il secondo punto del teorema master, ma non capisco come rendere $f(n) = Theta(n^(log_b a) )$
fissiamo che $n^{\log_9(3)} = n^{1/2}$
Grazie del consiglio!
ho provato ad applicare il Teorema master al secondo caso, dove richiede $T(n) = Theta(sqrt(n))$
e mi è venuto così:
per $alpha = 1/2 rArr f(n) = sqrt(n)$
dato che il primo punto del teorema master richiede che $ f(n) = O(n^(log_b a))$
[/quote]
attento il primo caso del master chiede che $f(n) \in O(n^{\log_b(a)-\epsilon})$ per $\epsilon > 0$ (e $<=1$ aggiungo).
e te non lo hai sottratto, ed anzi hai fissato un $\alpha$ troppo grande per render vera l'appartenenza.
No.
Hai fissato che $\alpha = 1/2$ quindi ci domandiamo se:
$n^(1/2) \in^? O(n^{\log_9(3) -\epsilon})$
l'unico epsilon che renderebbe vera l'appartenenza sarebbe $0$ cosa non possibile. Quindi non può andare bene, abbiamo due possibilità scegliere un $\alpha$ minore, oppure utilizzare il terzo caso del Master.
Per comodità cambiamo $\alpha = 1/3$ quindi:
$n^(1/3) \in O(n^{\log_9(3) -\epsilon})$ con $\epsilon = 1/6$ allora $T(n) \in \Theta(\sqrt(n))$
semplicemente utilizzi il ragionemante che hai fatto precedentemente, ma questa volta è il caso corretto
In pratica $n^\alpha$ con $\alpha = 1/2$ ha lo stesso ordine di grandezza di $n^{\log_9(3)}$ come scritto prima.
$f(n) = n^(1/2)$
$f(n) \in \Theta(n^{\log_9(3)})$ quindi $T(n) \in Theta(n^\alpha\log(n))$
"HeroGian":
[quote="hamming_burst"]Ciao,
passa per il Master Theorem.
Grazie del consiglio!
ho provato ad applicare il Teorema master al secondo caso, dove richiede $T(n) = Theta(sqrt(n))$
e mi è venuto così:
per $alpha = 1/2 rArr f(n) = sqrt(n)$
dato che il primo punto del teorema master richiede che $ f(n) = O(n^(log_b a))$
[/quote]
attento il primo caso del master chiede che $f(n) \in O(n^{\log_b(a)-\epsilon})$ per $\epsilon > 0$ (e $<=1$ aggiungo).
e te non lo hai sottratto, ed anzi hai fissato un $\alpha$ troppo grande per render vera l'appartenenza.
quindi $f(n) = O(n^(log_9 3) ) = O(sqrt(n))$ quindi per $alpha = 1/2 rArr T(n) = Theta(sqrt(n))$
Secondo voi può andare??
No.
Hai fissato che $\alpha = 1/2$ quindi ci domandiamo se:
$n^(1/2) \in^? O(n^{\log_9(3) -\epsilon})$
l'unico epsilon che renderebbe vera l'appartenenza sarebbe $0$ cosa non possibile. Quindi non può andare bene, abbiamo due possibilità scegliere un $\alpha$ minore, oppure utilizzare il terzo caso del Master.
Per comodità cambiamo $\alpha = 1/3$ quindi:
$n^(1/3) \in O(n^{\log_9(3) -\epsilon})$ con $\epsilon = 1/6$ allora $T(n) \in \Theta(\sqrt(n))$
"HeroGian":
Poi stavo provando a ragionare su $T(n) = Theta(sqrt(n)logn)$
sono quasi sicuro che devo applicare il secondo punto del teorema master, ma non capisco come rendere $f(n) = Theta(n^(log_b a) )$
semplicemente utilizzi il ragionemante che hai fatto precedentemente, ma questa volta è il caso corretto
In pratica $n^\alpha$ con $\alpha = 1/2$ ha lo stesso ordine di grandezza di $n^{\log_9(3)}$ come scritto prima.
$f(n) = n^(1/2)$
$f(n) \in \Theta(n^{\log_9(3)})$ quindi $T(n) \in Theta(n^\alpha\log(n))$
grazie per la risposta 
, penso di aver capito il procedimento più o meno..
Invece per quanto riguarda il quarto: $T(n) = Theta(n)$
In questo caso penso vada applicato il terzo punto del teorema master con $alpha = 1$, però non saprei come dimostrare che $n in Omega(n^(log_9 3 + epsilon))$
, penso di aver capito il procedimento più o meno..Invece per quanto riguarda il quarto: $T(n) = Theta(n)$
In questo caso penso vada applicato il terzo punto del teorema master con $alpha = 1$, però non saprei come dimostrare che $n in Omega(n^(log_9 3 + epsilon))$
"HeroGian":
Invece per quanto riguarda il quarto: $T(n) = Theta(n)$
In questo caso penso vada applicato il terzo punto del teorema master con $alpha = 1$, però non saprei come dimostrare che $n in Omega(n^(log_9 3 + epsilon))$
il terzo caso è quello che richiede un po' più di attenzione.
$n^1 \in^? \Omega(n^{0.5+\epsilon})$ con $\epsilon=0.5$
e c'è da dimostrare che: $\exists \c \in [0,1),m>=0\ :\ a*f(n/b) <= c*f(n)\ ,\ \forall n>=m$
cioè: $3(n/4)^1 = 3/4n <= cn\ if c>=3/4 \wedge m >= 1$
quindi $T(n) \in \Theta(f(n)) = \Theta(n)$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo