Ricorrenza A S D
Trovare l'andamento asintotico di
$T(n) = 4 T(n/2) + n^2log n$ col caso base $O(1)$
Arrivo a trovare un $O(n^3)$ Senza M T.
Qualcuno potrebbe dire "..ehm grazie al XXXXXXX!!"
Sapete fare di meglio?
$T(n) = 4 T(n/2) + n^2log n$ col caso base $O(1)$
Arrivo a trovare un $O(n^3)$ Senza M T.
Qualcuno potrebbe dire "..ehm grazie al XXXXXXX!!"
Sapete fare di meglio?
Risposte
fissato che $log(n) => \log_2(n)$ utilizziamo esempio il metodo dell'albero.
$n^2log_2(n) -> 4*n^2/2^2*\log_2(n/2^1) = 2^2*n^2/2^2(\log_2(n) - 1*\log_2(2)) -> ... -> 2^k*n^2/2^k(\log_2(n) - k)$
$T(1) = n/2^k = 1$ quando $k=\log_2(n)$
ci fermiamo a livello $h-1$ nell'albero immaginario:
$\sum_(k=1)^(\log_2(n)-1) 2^k*n^2/2^k(log_2(n) - k) = n^2sum_(k=1)^(\log_2(n)-1) \log_2(n) - k = n^2sum_(k=1)^(log_2(n)-1) k = n^2*(\log_2(n)(\log_2(n)-1))/2$
foglie: $4^(\log_2(n)) \in O(n^2)$
quindi $n^2*(\log_2(n)(\log_2(n)-1))/2 + O(n^2) \in O(n^2\log_2^2(n))$
salvo sviste la ricorrenza è poco più che quadratica, cosa hai utilizzato per trovarla cubica? un'approssimazione un po' grossa?
edit:
c'è un piccolo errore di indice vedere post successivi.
$n^2log_2(n) -> 4*n^2/2^2*\log_2(n/2^1) = 2^2*n^2/2^2(\log_2(n) - 1*\log_2(2)) -> ... -> 2^k*n^2/2^k(\log_2(n) - k)$
$T(1) = n/2^k = 1$ quando $k=\log_2(n)$
ci fermiamo a livello $h-1$ nell'albero immaginario:
$\sum_(k=1)^(\log_2(n)-1) 2^k*n^2/2^k(log_2(n) - k) = n^2sum_(k=1)^(\log_2(n)-1) \log_2(n) - k = n^2sum_(k=1)^(log_2(n)-1) k = n^2*(\log_2(n)(\log_2(n)-1))/2$
foglie: $4^(\log_2(n)) \in O(n^2)$
quindi $n^2*(\log_2(n)(\log_2(n)-1))/2 + O(n^2) \in O(n^2\log_2^2(n))$
salvo sviste la ricorrenza è poco più che quadratica, cosa hai utilizzato per trovarla cubica? un'approssimazione un po' grossa?
edit:
c'è un piccolo errore di indice vedere post successivi.
No Ham è perfetta!!! 
Forse si arriva analogamente a dimostrare che è teta di ciò che hai trovato.
Grazie!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Forse si arriva analogamente a dimostrare che è teta di ciò che hai trovato.
Grazie!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
"hamming_burst":
fissato che $log(n) => \log_2(n)$ utilizziamo esempio il metodo dell'albero.
$n^2log_2(n) -> 4*n^2/2^2*\log_2(n/2^1) $
Sì forse non capisco perché parti con questa parte di T(n)
Io avevo trovato per sostituzione con ipotesi grossolana... Niente di particolare.
Albero è molto più complicato da capire per me
Faccio prima a scrivere cosa mi è chiaro.
Ok, questo è il costo dell'ultima riga dell'albero con tutti i $T(1)$ :
Dove paghiamo "almeno" un $O(n^2)$
Sì anche questo, dopo un vuoto di memoria, mi è chiaro
Siamo in cima quindi $4^0$ moltiplicato il termine che prendiamo in esame:
$4^0*n^2log_2(n)$
Poi scendo dalla cima ed ho:
$ 4^1*n^2/2^2*\log_2(n/2^1) $
Se scendo ancora?
$ 4^2*(n/4)^2*\log_2(n/4) $
Ok, questo è il costo dell'ultima riga dell'albero con tutti i $T(1)$ :
"hamming_burst":
foglie: $4^(\log_2(n)) \in O(n^2)$
Dove paghiamo "almeno" un $O(n^2)$
"hamming_burst":
$n^2log_2(n) -> 4*n^2/2^2*\log_2(n/2^1) $
Sì anche questo, dopo un vuoto di memoria, mi è chiaro
Siamo in cima quindi $4^0$ moltiplicato il termine che prendiamo in esame:
$4^0*n^2log_2(n)$
Poi scendo dalla cima ed ho:
$ 4^1*n^2/2^2*\log_2(n/2^1) $
Se scendo ancora?
$ 4^2*(n/4)^2*\log_2(n/4) $
prima di tutto correggo due piccoli errori che mi son sfuggiti.
la forma generalizzata è: $2^k*n^2/2^k(\log_2(n) - (k-1))$ non $\log_2(n) - k$
questo perchè è scalato di uno rispetto alle potenze. E per esser pignoli fino all'osso, si parte da $k=2$ e non da $k=1$, perché al primo livello dell'albero, il $4$ non si nasconde algebricamente con potenza innalzata a $0$, come al solito; in questo caso sarebbe $2^1$ e non ha significato nella ricorsione a quel livello (si sostituisce solo al livello successivo); ma ha molta meno importanza rispetto al precedente "errore".
In conti sporchi, che non cambiano nulla sulla complessità finale:
$n^2\log_2(n) + n^2\sum_(k=2)^(\log_2(n)-1) (\log_2(n) - k + 1) = n^2\sum_(k=2)^(\log_2(n)-1) k =$
$= n^2\log_2(n) + n^2((\log_2(n)-2)(\log_2(n)+1))/2 = n^2\log_2(n) + 1/2*n^2(\log^2(n) - \log(n) - 2)$
quindi $n^2\log_2(n) + n^2/2(\log^2(n) - \log(n) - 2) + O(n^2) \in O(n^2\log_2^2(n))$
più precisa di così non so farla
poco importa perchè sono sforzi inutili, ma formalmente interessanti da sottolineare.
Sì, in generale se noti l'ultimo pezzo con costanti annesse, empiricamente dovrebbe esser valida una più generale $\Theta(n^2log(n))$ non penso si troppo complicato da dimostrare....
Per il metodo dell'albero ne riparliamo. Te lo ho mostrato solo perché ritengo esser una metodologia che aiuti ad astrarre la risoluzione delle ricorrenze, ed anche perché hai richiesto una conferma del risultato. Se non la comprendi o non l'hai fatta, prova ora a risolverla tramite iterazione...sulla base che ho scritto cambia molto poco.
Utilizzare sostituzione, sarebbe stato più sensato aver usato Master, così avevi una complessità in ipotesi e poi vedere se ci calzava tramite induzione (sostituzione)...andare a tentoni non è sempre una buona idea.
la forma generalizzata è: $2^k*n^2/2^k(\log_2(n) - (k-1))$ non $\log_2(n) - k$
questo perchè è scalato di uno rispetto alle potenze. E per esser pignoli fino all'osso, si parte da $k=2$ e non da $k=1$, perché al primo livello dell'albero, il $4$ non si nasconde algebricamente con potenza innalzata a $0$, come al solito; in questo caso sarebbe $2^1$ e non ha significato nella ricorsione a quel livello (si sostituisce solo al livello successivo); ma ha molta meno importanza rispetto al precedente "errore".
In conti sporchi, che non cambiano nulla sulla complessità finale:
$n^2\log_2(n) + n^2\sum_(k=2)^(\log_2(n)-1) (\log_2(n) - k + 1) = n^2\sum_(k=2)^(\log_2(n)-1) k =$
$= n^2\log_2(n) + n^2((\log_2(n)-2)(\log_2(n)+1))/2 = n^2\log_2(n) + 1/2*n^2(\log^2(n) - \log(n) - 2)$
quindi $n^2\log_2(n) + n^2/2(\log^2(n) - \log(n) - 2) + O(n^2) \in O(n^2\log_2^2(n))$
più precisa di così non so farla
poco importa perchè sono sforzi inutili, ma formalmente interessanti da sottolineare.
Forse si arriva analogamente a dimostrare che è teta di ciò che hai trovato.
Sì, in generale se noti l'ultimo pezzo con costanti annesse, empiricamente dovrebbe esser valida una più generale $\Theta(n^2log(n))$ non penso si troppo complicato da dimostrare....
Per il metodo dell'albero ne riparliamo. Te lo ho mostrato solo perché ritengo esser una metodologia che aiuti ad astrarre la risoluzione delle ricorrenze, ed anche perché hai richiesto una conferma del risultato. Se non la comprendi o non l'hai fatta, prova ora a risolverla tramite iterazione...sulla base che ho scritto cambia molto poco.
Utilizzare sostituzione, sarebbe stato più sensato aver usato Master, così avevi una complessità in ipotesi e poi vedere se ci calzava tramite induzione (sostituzione)...andare a tentoni non è sempre una buona idea.
Grazie Mitico!
Ultima cosa.
Cosa succede qui?
(Ho dato analisi 1 ed analisi 2 tipo 9 ed 8 anni fa
)
"hamming_burst":
$n^2\log_2(n) + n^2\sum_(k=2)^(\log_2(n)-1) (\log_2(n) - k + 1) = n^2\sum_(k=2)^(\log_2(n)-1) k =$
Ultima cosa.
Cosa succede qui?
(Ho dato analisi 1 ed analisi 2 tipo 9 ed 8 anni fa
)
"Giova411":
[quote="hamming_burst"]
$n^2\log_2(n) + n^2\sum_(k=2)^(\log_2(n)-1) (\log_2(n) - k + 1) = n^2\sum_(k=2)^(\log_2(n)-1) k =$
Ultima cosa.
Cosa succede qui?
[/quote]utilizziamo $n$ invece che $\log n$
$\sum_{i=0}^{n} (n-k) = \sum_{i=0}^{n}k$
prova a srotolare la sommatoria:
$(n-0) + (n-1) + .... + (n-(n-1)) + (n-n) = 0 + 1 + ... + (n-1) + n$
semplicemente un'uguaglianza con un sommatoria con ordine invertito, più semplice da trattare
per gli indici con $k=2$, $-k+1$, ... utilizza lo stesso ragionamento con un es. prova a sostituire $n$ con $10$ e vedrai che i conti tornano.
Ti ho appena scritto in PRIVATO!!!! 
Grande HAM!!!
...e grazie ancora per tutti i consigli tecnico/tattici
!!!!
PS: sì voglio usare le faccette che non usa mai nessuno!!!! tipo questa --->
Grande HAM!!!
...e grazie ancora per tutti i consigli tecnico/tattici
!!!!PS: sì voglio usare le faccette che non usa mai nessuno!!!! tipo questa --->
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo