[Algoritmi][ASD]Risoluzione ricorrenza - metodo iterativo
Salve
Stavo provando a calcolare il tempo di esecuzione di tale ricorrenza:
\( T(n) = 2T(\frac{n}{2}) + n^3 \)
I miei calcoli:
\( T(\frac{n}{2}) = 4T(\frac{n}{4}) + \frac{1}{4}n^3 + n^3 \)
\( T(\frac{n}{4}) = 8T(\frac{n}{8}) + \frac{1}{16}n^3 + \frac{1}{4}n^3 + n^3 \)
\( T(\frac{n}{2^i}) = 2^iT(\frac{n}{2^i}) + n^3 \sum_{j=0}^{i-1} 2^{-2j} \)
essendo \(T(\frac{n}{2^i}) == T(1)\) quando \((\frac{n}{2^i}) == 1 \) cioè quando \(i=\log_2 n\) allora:
\(T(\frac{n}{2^{\log_2 n}}) = 2^{\log_2 n}T(\frac{n}{2^{\log_2 n}}) + n^3 \sum_{j=0}^{\log_2 (n) - 1} 2^{-2j} =\)
essendo quest'ultima una serie geometrica la sua somma e pari a:
\( = nT(1) + n^3[\frac{2^{-2(\log_2 (n) - 1 + 1)} - 1}{2^{-2} - 1}] =\)
\( = \theta(n) + n^3[\frac{n^{-2} - 1}{\frac{3}{4}}] = \)
\( = \theta(n) + n^3[\frac{4n^{-2} - 4}{3}] = \)
\( = \theta(n) + \frac{4}{3}(n-n^3) = \)
\( T(n) = \theta(n) + \theta(n^3) = \theta(n^3) \)
La mia domanda è che non so se l'ho svolta correttamente e quindi il risultato è giusto o meno.
Potreste aiutarmi?
Stavo provando a calcolare il tempo di esecuzione di tale ricorrenza:
\( T(n) = 2T(\frac{n}{2}) + n^3 \)
I miei calcoli:
\( T(\frac{n}{2}) = 4T(\frac{n}{4}) + \frac{1}{4}n^3 + n^3 \)
\( T(\frac{n}{4}) = 8T(\frac{n}{8}) + \frac{1}{16}n^3 + \frac{1}{4}n^3 + n^3 \)
\( T(\frac{n}{2^i}) = 2^iT(\frac{n}{2^i}) + n^3 \sum_{j=0}^{i-1} 2^{-2j} \)
essendo \(T(\frac{n}{2^i}) == T(1)\) quando \((\frac{n}{2^i}) == 1 \) cioè quando \(i=\log_2 n\) allora:
\(T(\frac{n}{2^{\log_2 n}}) = 2^{\log_2 n}T(\frac{n}{2^{\log_2 n}}) + n^3 \sum_{j=0}^{\log_2 (n) - 1} 2^{-2j} =\)
essendo quest'ultima una serie geometrica la sua somma e pari a:
\( = nT(1) + n^3[\frac{2^{-2(\log_2 (n) - 1 + 1)} - 1}{2^{-2} - 1}] =\)
\( = \theta(n) + n^3[\frac{n^{-2} - 1}{\frac{3}{4}}] = \)
\( = \theta(n) + n^3[\frac{4n^{-2} - 4}{3}] = \)
\( = \theta(n) + \frac{4}{3}(n-n^3) = \)
\( T(n) = \theta(n) + \theta(n^3) = \theta(n^3) \)
La mia domanda è che non so se l'ho svolta correttamente e quindi il risultato è giusto o meno.
Potreste aiutarmi?
Risposte
I calcoli mi sembrano corretti e dovrebbe esserlo anche il risultato (applicando il teorema Master viene infatti uguale).
grazie mille per la risposta
Scusate il disturbo 
Io ho appena iniziato a vedere le ricorrenze, premetto questo.
Non capisco cosa avviene tra questi passaggi che, a voi, possono sembrare banali.
Capisco la parte dopo dove si arriva alla serie geometrica.
Capisco anche che iteriamo ed immagino l'albero ricorsivo che si ramifica sempre più:
prime 2 chiamate ricorsive, poi dopo saranno 4 e così via.
Io ho appena iniziato a vedere le ricorrenze, premetto questo.
Non capisco cosa avviene tra questi passaggi che, a voi, possono sembrare banali.
"HackAlli":
.. tempo di esecuzione di tale ricorrenza:
\( T(n) = 2T(\frac{n}{2}) + n^3 \)
I miei calcoli:
\( T(\frac{n}{2}) = 4T(\frac{n}{4}) + \frac{1}{4}n^3 + n^3 \)
\( T(\frac{n}{4}) = 8T(\frac{n}{8}) + \frac{1}{16}n^3 + \frac{1}{4}n^3 + n^3 \)
...
Capisco la parte dopo dove si arriva alla serie geometrica.
Capisco anche che iteriamo ed immagino l'albero ricorsivo che si ramifica sempre più:
prime 2 chiamate ricorsive, poi dopo saranno 4 e così via.
C'é qualcuno che mi illumina? 
La parte a sinistra dell'uguale era in effetti sbagliata, avrebbe dovuto essere T(n) in tutti i casi. Quello che fai è comunque semplicemente sostituire alla chiamata ricorsiva la sua definizione con il valore cambiato di n.
Sì, ma il mio problema è che, a volte, riesco a trovarmi coi passaggi, molte altre no.
Forse mi confondo nelle sostituzioni perché sono ancora principiante...
Dovrebbero essere una "matematica semplice"...
(SPERO SIA COSI') =)
Forse mi confondo nelle sostituzioni perché sono ancora principiante...
Dovrebbero essere una "matematica semplice"...
(SPERO SIA COSI') =)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo