Equazione di ricorrenza dell'algoritmo di strassen
ho questa equazione di ricorrenza e devo determinare la soluzione:
$\T(1) = c$
$\T(n) = 7T(n/2) + 18(n/2)^2$
come va risolta? con il teorema principale?
se si, come mi devo comportare con quel $\18(n/2)^2$?
sul mio testo è riportata solo la soluzione che è T(n) = O(n^(log base2 di 7))
*edit*
ho trovato un procedimento, ditemi se va bene:
$\T(1) = c$
$\T(n) = 7T(n/2) + 18(n/2)^2$
$\T(1) = c$
$\T(n) = 7T(n/2) + \Theta(n^2)$
a=7
b=2
d(b)=4
a>d(b) quindi T(n) = O(n^(logb di a)) e quindi O(n^(log2 di 7))
$\T(1) = c$
$\T(n) = 7T(n/2) + 18(n/2)^2$
come va risolta? con il teorema principale?
se si, come mi devo comportare con quel $\18(n/2)^2$?
sul mio testo è riportata solo la soluzione che è T(n) = O(n^(log base2 di 7))
*edit*
ho trovato un procedimento, ditemi se va bene:
$\T(1) = c$
$\T(n) = 7T(n/2) + 18(n/2)^2$
$\T(1) = c$
$\T(n) = 7T(n/2) + \Theta(n^2)$
a=7
b=2
d(b)=4
a>d(b) quindi T(n) = O(n^(logb di a)) e quindi O(n^(log2 di 7))
Risposte
Ciao,
non conoscevo le costanti nascoste di dell'equazione di ricorrenza di questo algoritmo, interessante. Avevo un'idea per via delle sottomatrici, ma non sapevo questo
ci sono vari modi per risolverla, il Master Theorem è uno.
Visto che lo hai utilizzato:
- ti manca una condizione per quale $\epsilon>0$, $cf(n^2) in O(n^{log_{2}(7) - \epsilon})$?
- cosa è $d(b)$?
Ma ce ne sono di più interessanti.
Visto che hai riportato pure le costanti, calcoliamo per bene tutto
ipotizziamo $n$ numero intero, potenza esatta di $2$. Utilizziamo il metodo dell'albero di ricorsione che produce un'ottima (non in senso algoritmico) limitiazione asintotica superiore:
$(9/2)n^2 -> (9/2)7^1*(n/(2^1))^2 -> (9/2)7^2n^2/4^2 ... -> (9/2)7^i\n^2/4^i -> ... -> (9/2)7^(h-1)\n^2/(4^(h-1)) -> n^{log_{2}(7)}*T(1)$
altezza albero $h=log_{2}(n)$
$T(n=1) = n/2^i=1$ quando $i=log_{2}(n)$
sommiamo i nodi interni:
$\sum_{i=0}^{log_{2}(n)-1} (9/2)7^i\n^2/4^i = (9/2)\sum_{i=0}^{log_{2}(n)-1} 7^i\n^2/4^i = (9/2)n^2\sum_{i=0}^{log_{2}(n)-1} (7/4)^i$ che è una serie geometrica crescente, perciò:
$(9/2)n^2\sum_{i=0}^{log_{2}(n)-1} (7/4)^i = (9/2)n^2*(((7/4)^{(log_{2}(n)-1)+1}-1)/(7/4 - 1)) = (9/2)n^2(((n^{log_{2}(7)}/n^2) -1)/(3/4)) = 6n^{log_{2}(7)} - 6n^2$
le foglie dell'albero sono: $7^{log_{2}(n)} = n^{log_{2}(7)} in \O(n^{log_{2}(7)})$
sommiamo il tutto: $6n^{log_{2}(7)} - 6n^2 + \O(n^{log_{2}(7)}) in O(n^{log_{2}(7)})$
Perciò l'equazione risulta appartenere alla classe di complessità $O(n^{log_{2}(7)})$
Se hai dubbi chiedi pure
PS: il metodo dell'albero te lo ho messo solo come modo per calcolare la stessa complessità vista con il Master Theorem.
non conoscevo le costanti nascoste di dell'equazione di ricorrenza di questo algoritmo, interessante. Avevo un'idea per via delle sottomatrici, ma non sapevo questo
ci sono vari modi per risolverla, il Master Theorem è uno.
Visto che lo hai utilizzato:
- ti manca una condizione per quale $\epsilon>0$, $cf(n^2) in O(n^{log_{2}(7) - \epsilon})$?
- cosa è $d(b)$?
Ma ce ne sono di più interessanti.
Visto che hai riportato pure le costanti, calcoliamo per bene tutto
ipotizziamo $n$ numero intero, potenza esatta di $2$. Utilizziamo il metodo dell'albero di ricorsione che produce un'ottima (non in senso algoritmico) limitiazione asintotica superiore:
$(9/2)n^2 -> (9/2)7^1*(n/(2^1))^2 -> (9/2)7^2n^2/4^2 ... -> (9/2)7^i\n^2/4^i -> ... -> (9/2)7^(h-1)\n^2/(4^(h-1)) -> n^{log_{2}(7)}*T(1)$
altezza albero $h=log_{2}(n)$
$T(n=1) = n/2^i=1$ quando $i=log_{2}(n)$
sommiamo i nodi interni:
$\sum_{i=0}^{log_{2}(n)-1} (9/2)7^i\n^2/4^i = (9/2)\sum_{i=0}^{log_{2}(n)-1} 7^i\n^2/4^i = (9/2)n^2\sum_{i=0}^{log_{2}(n)-1} (7/4)^i$ che è una serie geometrica crescente, perciò:
$(9/2)n^2\sum_{i=0}^{log_{2}(n)-1} (7/4)^i = (9/2)n^2*(((7/4)^{(log_{2}(n)-1)+1}-1)/(7/4 - 1)) = (9/2)n^2(((n^{log_{2}(7)}/n^2) -1)/(3/4)) = 6n^{log_{2}(7)} - 6n^2$
le foglie dell'albero sono: $7^{log_{2}(n)} = n^{log_{2}(7)} in \O(n^{log_{2}(7)})$
sommiamo il tutto: $6n^{log_{2}(7)} - 6n^2 + \O(n^{log_{2}(7)}) in O(n^{log_{2}(7)})$
Perciò l'equazione risulta appartenere alla classe di complessità $O(n^{log_{2}(7)})$
Se hai dubbi chiedi pure
PS: il metodo dell'albero te lo ho messo solo come modo per calcolare la stessa complessità vista con il Master Theorem.
d(b) è la funzione guida, il mio testo la presenta cosi.
per curiosità su che testo hai studiato? perche su quelli che ho io le equazioni di ricorrenza sono spiegate malissimo.
per curiosità su che testo hai studiato? perche su quelli che ho io le equazioni di ricorrenza sono spiegate malissimo.
"mathix":
d(b) è la funzione guida, il mio testo la presenta cosi.
"funzione guida" mai sentita. Non riesco ad immaginare il suo utilizzo, me lo spiegheresti, se vuoi
Comunque ti è chiaro il procedimento, manca sempre $\epsilon$ da enunciare...
per curiosità su che testo hai studiato? perche su quelli che ho io le equazioni di ricorrenza sono spiegate malissimo.
vedi qua (algoritmica)
il primo in elenco è davvero ben fatto e completo. Poi c'è il classico Cormen, il migliore, ma non gradito a tutti
se vuoi ultieriore materiale di studio poi vedi la sezione Dispense.
per funzione guida il testo che ho intende la f(n) di aT(n/b) + f(n)
il testo che usiamo (lo trovi a questo link http://www.sci.unich.it/~acciaro/corsoASD.pdf) non riporta affatto la $\epsilon$
se ti va dai un'occhiata a pagina 71
il testo che usiamo (lo trovi a questo link http://www.sci.unich.it/~acciaro/corsoASD.pdf) non riporta affatto la $\epsilon$
se ti va dai un'occhiata a pagina 71
"mathix":
per funzione guida il testo che ho intende la f(n) di aT(n/b) + f(n)
il testo che usiamo (lo trovi a questo link http://www.sci.unich.it/~acciaro/corsoASD.pdf) non riporta affatto la $\epsilon$
se ti va dai un'occhiata a pagina 71
ho dato un'occhiata un po' veloce, mi sembra di capire che utilizza un'approssimazione sui numero di nodi in ambiezza per livello dell'albero (se sai il Master è stato teorizzato utilizzando il metodo dell'albero) e il numero di dimezzamenti che riducono o amplificano la profondità. Il principio è simile $\epsilon$ aumenta o diminuisce la classe di complessità dell'equazione (ipotizzata), e questo implica ipotizzare un albero più profondo o pià ampio. In soldoni mi sembra di aver capito ciò. Penso siano sistemi simili.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo