Caso particolare del teorema Master
E' il secondo caso generalizzato che dice:
Se
[tex]f(n)=\theta(n^{\log_b(a)}\log_b(n)^k)[/tex]
Allora:
[tex]T(n)=\theta(n^{\log_b(a)}\log(n)^{k+1}[/tex]
Io ho questa equazione:
[tex]T(n)=4T(n/2)+n^2\log^2(n)[/tex]
Ho un pò di problemi, sulla prima parte del teorema ci siamo che sia [tex]\theta(n^{\log_b(a)}[/tex]
Ma poi come si continua? cioè il fattore k io l' avrei considerato come 2, ma [tex]\log^2(n)[/tex] è diverso da [tex]\log(n)^2[/tex] quindi come continuare?
Poi un' altra cosetta.
Quest' altra:
[tex]T(n)=T(n-1)+n[/tex]
Per il telescoping viene [tex]\theta(n^2)[/tex]
Se volessi usare l' albero avrei:
[tex]n-->(n-1)-->(n-2)--->(n-k)[/tex]
[tex]\theta(1)[/tex] quando [tex]k=n[/tex] avrei:
[tex]\sum_{k=0}^{n-1}n-k[/tex]
Ora dovrei separare le sommatorie....e qui mi perdo dalla casa...
[tex]\sum_{n=1}^{n}n-\sum_{k=0}^{n-1}k[/tex]
Penso che sia sbagliato, ma supponiamo per assurdo che sia vero....avrei in entrambi i casi la somma dei primi n naturali e quindi soluzione [tex]\theta(n^2)[/tex] ?
Se
[tex]f(n)=\theta(n^{\log_b(a)}\log_b(n)^k)[/tex]
Allora:
[tex]T(n)=\theta(n^{\log_b(a)}\log(n)^{k+1}[/tex]
Io ho questa equazione:
[tex]T(n)=4T(n/2)+n^2\log^2(n)[/tex]
Ho un pò di problemi, sulla prima parte del teorema ci siamo che sia [tex]\theta(n^{\log_b(a)}[/tex]
Ma poi come si continua? cioè il fattore k io l' avrei considerato come 2, ma [tex]\log^2(n)[/tex] è diverso da [tex]\log(n)^2[/tex] quindi come continuare?
Poi un' altra cosetta.
Quest' altra:
[tex]T(n)=T(n-1)+n[/tex]
Per il telescoping viene [tex]\theta(n^2)[/tex]
Se volessi usare l' albero avrei:
[tex]n-->(n-1)-->(n-2)--->(n-k)[/tex]
[tex]\theta(1)[/tex] quando [tex]k=n[/tex] avrei:
[tex]\sum_{k=0}^{n-1}n-k[/tex]
Ora dovrei separare le sommatorie....e qui mi perdo dalla casa...
[tex]\sum_{n=1}^{n}n-\sum_{k=0}^{n-1}k[/tex]
Penso che sia sbagliato, ma supponiamo per assurdo che sia vero....avrei in entrambi i casi la somma dei primi n naturali e quindi soluzione [tex]\theta(n^2)[/tex] ?
Risposte
Ma scusa, qua non puoi applicare il Master Theorem. L'unica possibilità potresti vedere se c'è una limitazione inferiore $Omega()$ cioè il terzo caso, ma si vede facilmente che non è vero.
Hai un po' di confusione sul Master Theorem, ti consiglio di rivederlo, penso che tu abbia visto ciò che è scritto su wikipedia, lascia stare applica solo ciò che hai studiato sui libri (ti consiglio di leggere il Cormen).
Quello che vuoi applicare te è componente della Dimostrazione del Mater Theorem.
Poi è facile vedere che $log^k(n) != log(n)^k$ perciò non applicabile con la teoria. Basta che pensare che $log(n)^2 = 2(log(n)$ in $Theta(log(n))$ e $log^2(n) in Omega(logn)$.
Spero sia più chiaro.
la seconda domanda:
quella separazione mi sa che è un qualcosa che non si può fare, ma perchè complicarsi la vita, vedi facilemente che è una serie aritmetica al contrario $n-0 + n-1 ....$ invece che $0 + 1 + ....$, perciò:
$sum_{k=0}^{n-1} n-k = sum_{h=1}^{n} h = (n(n+1))/2 in Theta(n^2)$
un altro modo di risolvere queste ricorrenze, solo per darti un'altra possibile risoluzione, è usare la teoria delle "Ricorrenze lineari di ordine costante", che ti da lo stesso risultato.
Hai un po' di confusione sul Master Theorem, ti consiglio di rivederlo, penso che tu abbia visto ciò che è scritto su wikipedia, lascia stare applica solo ciò che hai studiato sui libri (ti consiglio di leggere il Cormen).
Quello che vuoi applicare te è componente della Dimostrazione del Mater Theorem.
Poi è facile vedere che $log^k(n) != log(n)^k$ perciò non applicabile con la teoria. Basta che pensare che $log(n)^2 = 2(log(n)$ in $Theta(log(n))$ e $log^2(n) in Omega(logn)$.
Spero sia più chiaro.
la seconda domanda:
quella separazione mi sa che è un qualcosa che non si può fare, ma perchè complicarsi la vita, vedi facilemente che è una serie aritmetica al contrario $n-0 + n-1 ....$ invece che $0 + 1 + ....$, perciò:
$sum_{k=0}^{n-1} n-k = sum_{h=1}^{n} h = (n(n+1))/2 in Theta(n^2)$
un altro modo di risolvere queste ricorrenze, solo per darti un'altra possibile risoluzione, è usare la teoria delle "Ricorrenze lineari di ordine costante", che ti da lo stesso risultato.
Ah grazie, benissimo, soprattutto l' ultima cosa, non ci avevo pensato 
Concordo con ham_burst, ma separare le serie non è errato. È errato il modo in cui l'hai fatto: $n$ non varia con la serie, rimane costante e quindi viene $n^2 - (n-1)n/2$ che coincide con il risultato ottenuto tramite la pura e semplice applicazione della serie di Gauss.
ah interessante, si avevo pensato che estrapolando $n$ dalla serie rimanesse costante, ma non sapevo come si potesse sistemare quello detto da Dereios. Quello che hai detto però sulla serie me lo segno, può tornami utile 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo