[Algoritmi] Risoluzione equazioni di ricorrenza

[iggy]

Credo tu non abbia capito come funziona il teorema master. Ci sono tre casi da considerare e se la tua ricorrenza rispetta tutte le ipotesi di uno di questi casi, allora il teorema ti fornisce la soluzione. Ad una occhiata veloce credo che il secondo esercizio rientri in un caso diverso e che quindi il risultato sia anche diverso. Ma il teorema è solo una scorciatoia. È possibile seguire la strada che ho usato nel mio post precedente per arrivare agli stessi risultati.

In che caso rientra a questo punto?

Ad ogni modo ho provato a risolverlo con il metodo iterativo (perchè con gli alberi non mi trovo) e al caso finale cioè t(1), mi risulta è: \(\displaystyle n^2*T(1) + \sum_{k=0}^{log_4 n -1} 8^{k-1}*d((n/4^{k-1})\sqrt(n/4^{k-1})) \) che togliendo le varie n dalla sommatoria e semplificandola mi rimane sono sommatoria di 1^k che però non mi sembra abbia troppo senso.

Grazie.

[apatriarca]

No, mi sbagliavo. È esattamente lo stesso caso ed in effetti il risultato è quello. Si vede anche osservando che ogni livello dell'albero somma a \(n^{3/2}\) e ci sono \(\log n\) livelli.

[apatriarca]

Mostra i passaggi.. Non mi è chiaro come arrivi a tale espressione.

[iggy]

Mostra i passaggi.. Non mi è chiaro come arrivi a tale espressione.

\(\displaystyle t(n) = 8T(n/4) + d(n\sqrt(n)) \)
\(\displaystyle t(n/4) = 8T(n/16) + d((n/4)\sqrt(n/4)) \) (sostituisco t(n/4) nell'equazione)
\(\displaystyle t(n) = 8[8T(n/16) + d((n/4)\sqrt(n/4)) + d(n\sqrt n) = 64T(n/16)+8d((n/4)*\sqrt(n/4))+d(n\sqrt(n)) \)

generalizzando la formula è: \(\displaystyle T(n) = 8^iT(n/4^i) + 8^{i-1}d((n/4^{i-1})\sqrt(n/4^{i-1}))+...+8^1d((n/4^{0})\sqrt(n/4^{0})) \)

sostituisco i con \(\displaystyle log_4 n \) e questa è la equazione da risolvere

\(\displaystyle n^2*T(1) + \sum_{k=0}^{log_4 n -1} 8^{k-1}*d((n/4^{k-1})\sqrt(n/4^{k-1})) \)

[apatriarca]

Si vede abbastanza facilmente che i termini dentro la sommatoria sono uguali a (sostituisco \(s = k-1\) per comodità):
\[ 8^s\,d\,\frac{n}{4^s}\,\sqrt{\frac{n}{4^s}} = 8^s\,d\,\,\frac{n^{3/2}}{8^s} = d\,n^{3/2}. \]
La sommatoria vale quindi \(d\,n^{3/2}\,\log\,n.\) Non mi è chiaro da dove venga fuori quel \(n^2\). Abbiamo
\[ 8^{\log_4 n} = 4^{(3/2) \log_4 n} = 4^{\log_4 n^{3/2}} = n^{3/2}. \]
Siccome \(T(1)\) è supposto costante abbiamo quindi che la complessità è determinata dalla sommatoria e uguale a \(\Theta(n^{3/2}\,\log n).\)

[iggy]

Si vede abbastanza facilmente che i termini dentro la sommatoria sono uguali a (sostituisco \(s = k-1\) per comodità):
\[ 8^s\,d\,\frac{n}{4^s}\,\sqrt{\frac{n}{4^s}} = 8^s\,d\,\,\frac{n^{3/2}}{8^s} = d\,n^{3/2}. \]
La sommatoria vale quindi \(d\,n^{3/2}\,\log\,n.\) Non mi è chiaro da dove venga fuori quel \(n^2\). Abbiamo
\[ 8^{\log_4 n} = 4^{(3/2) \log_4 n} = 4^{\log_4 n^{3/2}} = n^{3/2}. \]
Siccome \(T(1)\) è supposto costante abbiamo quindi che la complessità è determinata dalla sommatoria e uguale a \(\Theta(n^{3/2}\,\log n).\)

capito, grazie.