Pages: [1]   Go Down
Print
Author Topic: Ricorrenza  (Read 1046 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« on: 06-02-2012, 10:12:59 »

Ho svolto questa ricorrenza:
T(n)=4T(n/2)+n^2log(n)
E' una ricorrenza presente nel libro di testo a pagina 63, numero 4.3-4. Prima ho visto se si poteva applicare il metodo dell'esperto, ma il terzo caso non veniva soddisfatta la condizione di regolarità.
Quindi ho applicato il metodo della sostituzione, e ho trovato un limite asintotico superiore dato da O(n^2).
E' corretto il ragionamento? Grazie a chiunque risponda
Logged
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #1 on: 06-02-2012, 13:58:06 »

non dovrebbe risultare cosi, infatti applicando il secondo caso generalizzato del teorema master avrai come risultato Teta(n^2 * log^2), l'abbiamo fatto anche a lezione e questo era il risultato 
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #2 on: 06-02-2012, 15:13:30 »

Scusami mi puoi dire come mai applichi questo caso? Grazie
Ok Grazie ho visto dalle slides del prof ed ho visto che per k=1, siamo nel secondo caso generalizzato.
« Last Edit: 06-02-2012, 15:21:10 by vincenzo86 » Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #3 on: 15-02-2012, 11:37:41 »

Altra ricorrenza:
T(n)=8T(n/2)+n^2log^2n
Applicando il teorema master sono nel 2 caso generalizzato per k=2; quindi la soluzione è T(n)=\theta(n^2log^3n)
Le altre soluzioni sono:
T(n)=\theta(n^2log^2n)
T(n)=\theta(n^3)
T(n)=\theta(n^3log^3n)
Logged
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #4 on: 15-02-2012, 12:42:29 »

Il II caso generalizzato possiamo applicarlo solo se avessimo avuto 4T(n/2), non 8T(n/2) infatti in quest'ultimo caso le chiamate ricorsive hanno un costo di n^3, e non puoi dire che sono Teta di(n^2 * log^2).. Quindi andando per logica, dato che sono le chiamate ricorsive ad avere un costo maggiore, la risposta "dovrebbe" essere la seconda tra quelle altre elencate( n^3 ), ma non ne sono sicurissimo perchè l'unico modo per dimostrarlo è per sostituzione e alla fine risulta un integrale non proprio immediato..
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #5 on: 15-02-2012, 15:30:56 »

Il II caso generalizzato possiamo applicarlo solo se avessimo avuto 4T(n/2), non 8T(n/2) infatti in quest'ultimo caso le chiamate ricorsive hanno un costo di n^3, e non puoi dire che sono Teta di(n^2 * log^2).. Quindi andando per logica, dato che sono le chiamate ricorsive ad avere un costo maggiore, la risposta "dovrebbe" essere la seconda tra quelle altre elencate( n^3 ), ma non ne sono sicurissimo perchè l'unico modo per dimostrarlo è per sostituzione e alla fine risulta un integrale non proprio immediato..
Scusami la ricorrenza è T(n)=4T(n/2)+n^2log^2n.
Mi sono confuso con il primo fattore a scrivere.
Così infatti siamo nel secondo caso generalizzato, che poi è quello che ho scritto... Se fosse stato 8T(n/2), sarebbe stato O(n^3) per il primo caso del teorema master.
Al limite poi si può fare per sostituzione o telescoping, ma non era questo l'esercizio.
Logged
ZlatanCld
Matricola
*
Offline Offline

Posts: 46


« Reply #6 on: 15-02-2012, 15:47:22 »

Ah ok perfetto, ora i conti tornano 
Logged
Pages: [1]   Go Up
Print
Jump to: