[Algoritmi] Risoluzione equazioni di ricorrenza
Salve a tutti, sto trovando problemi a risolvere queste due equazioni ricorsive delle quali devo calcolare la complessità:
1) \(\displaystyle T(n) = 4T(n/2)+ Θ(n^2*logn) \);
2) \(\displaystyle T(n) = 8T(n/4) + Θ(n*sqrt(n)) \).
Ho provato sia il con il metodo iterativo, sia con il metodo di sostituzione, ma ad un certo punto mi blocco. Qualcuno può darmi un mano?
Grazie.
1) \(\displaystyle T(n) = 4T(n/2)+ Θ(n^2*logn) \);
2) \(\displaystyle T(n) = 8T(n/4) + Θ(n*sqrt(n)) \).
Ho provato sia il con il metodo iterativo, sia con il metodo di sostituzione, ma ad un certo punto mi blocco. Qualcuno può darmi un mano?
Grazie.
Risposte
Vista la forma delle due equazioni di ricorrenza la prima strategia a cui penserei è il master theorem. Hai mai visto questo teorema?
"apatriarca":
Vista la forma delle due equazioni di ricorrenza la prima strategia a cui penserei è il master theorem. Hai mai visto questo teorema?
So cos'è ma non l'abbiamo fatto a lezioni, quindi teoricamente non dovrei usarlo.
Per esempio la prima con il teorema principale dovrebbe venire log base 2 di 4 = 2 -> n^2 che è maggiore di \(\displaystyle n^2*logn \) quindi \(\displaystyle Θ(n^2) \). Corretto?
Ora provo con il metodo di sostituzione a trovare il limite superiore, cioè cerco una costante c per cui vale che\(\displaystyle T(n)<=c*n^2 \)
\(\displaystyle T(n) = 4T(n/2) + Θ(n^2*logn) <= 4c(n/2)^2+d((n/2)^2 * log(n/2)) = cn^2+d((n^2/4)*log(n/2)) = cn^2 + d*((n^2/4)*(logn-log2)) = cn^2 + d*(n^2/4)*logn - d*(n^2/4)*log2 <= cn^2 \)
A questo punto mi blocco: non capisco se c'è un errore.
No, \(n^2 < n^2 \log\,n\).
"apatriarca":
No, \(n^2 < n^2 \log\,n\).
Caspita che erroraccio.
A questo punto allora la situazione che mi ritrovo è:
\(\displaystyle t(n) <= 4c(n^2/4)*log(n/2)+d(n^2/4*log(n/2)
= cn^2*logn-cn^2*log2 + d(n^2/4)*logn-d(n^2/4)*log2 <= cn^2*logn \)
quindi la disequazione è vera se \(\displaystyle cn^2*log2 + d(n^2/4)*log2 >= d(n^2/4)*logn \) . Corretto? Perchè comunque non riesco a risolverla.
Non ho controllato i tuoi calcoli ma in base al master theorem dovresti avere che \(T(n) = \Theta(n^2\,\log^2\,n).\) Posso quindi supporre che se non riesci a risolvere quella disuguaglianza è perché è falsa. Così a prima vista probabilmente il metodo dell'albero potrebbe essere quello più efficace in questo caso.
Da dove salta fuori quel alla seconda sul logaritmo?
Se pensi all'albero di ricorsione, abbiamo che l'altezza dell'albero è uguale a \(\log_2 n.\) Ad ogni livello avremo \(4^k\) nodi con un \((n^2/4^k)\,\log_2 (n/2^k) = (n^2/4^k)\,(\log_2 n - k) \leq (n^2/4^k)\,\log_2 n.\) A questo punto possiamo suonare tutti i contributi al livello \(k\) ottenendo \(n^2\,\log_2 n\) e siccome ci sono \(\log_2 n\) livelli otteniamo il risultato \(n^2\,\log^2_2 n\)
"apatriarca":
Se pensi all'albero di ricorsione, abbiamo che l'altezza dell'albero è uguale a \(\log_2 n.\) Ad ogni livello avremo \(4^k\) nodi con un \((n^2/4^k)\,\log_2 (n/2^k) = (n^2/4^k)\,(\log_2 n - k) \leq (n^2/4^k)\,\log_2 n.\) A questo punto possiamo suonare tutti i contributi al livello \(k\) ottenendo \(n^2\,\log_2 n\) e siccome ci sono \(\log_2 n\) livelli otteniamo il risultato \(n^2\,\log^2_2 n\)
Ok ho capito il ragionamento, grazie. Ma nel teorema master come ci si accorge che, in questo caso, la complessità è \(\displaystyle Θ(n^2∗log^2n) \) anzichè \(\displaystyle Θ(n^2∗logn) \) come avevo fatto io?
)
Quindi se utilizziamo il teorema master nel secondo esercizio: \(\displaystyle T(n)=8T(n/4)+Θ(n∗sqrt(n)) \)
\(\displaystyle log_4 8 = 3/2 \), quindi \(\displaystyle n^{3/2} = n∗sqrt(n) \) perchè \(\displaystyle n^1*n^1/2 = n^{3/2} \) e la complessità sarà \(\displaystyle Θ(n^{3/2}*logn) \)? Sbaglio qualcosa?
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.
"apatriarca":
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.
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.
Mostra i passaggi.. Non mi è chiaro come arrivi a tale espressione.
"apatriarca":
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})) \)
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).\)
\[ 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).\)
"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).\)
capito, grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo