Pages: [1]   Go Down
Print
Author Topic: equazione di ricorrenza  (Read 1899 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
francesco85
Apprendista Forumista
**
Offline Offline

Posts: 262



« on: 07-12-2010, 16:52:24 »

ragazzi a voi questa è equazione quanto risulta?

T(n)=2T(n/3)+2T(n/9)+n

a me risulta O(n), ma in alcuni esercizi ho trovato come soluzione O(nlogn).

inoltre volevo chiedere come risolvete questa serie:

sommatoria(i=0 ad n-1)  i2i

grazie in anticipo
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 07-12-2010, 17:58:43 »

Quanto alla prima, vedrò più tardi, per la seconda, se non sbaglio si tratta di una serie geometrica, o sbaglio?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #2 on: 07-12-2010, 23:17:54 »

e mi sa anche a me! dovrebbe fare O(n2^n)
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
francesco85
Apprendista Forumista
**
Offline Offline

Posts: 262



« Reply #3 on: 08-12-2010, 13:07:42 »

e mi sa anche a me! dovrebbe fare O(n2^n)

O(n2n) ti riferisci alla serie?
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 on: 08-12-2010, 14:09:14 »

inoltre volevo chiedere come risolvete questa serie:

sommatoria(i=0 ad n-1)  i2i

grazie in anticipo
qui ne avevo risolto una molto simile e mi dava O(n2^{n})

ragazzi a voi questa è equazione quanto risulta?

T(n)=2T(n/3)+2T(n/9)+n

a me risulta O(n), ma in alcuni esercizi ho trovato come soluzione O(nlogn)

T(n)\ =\ 2T(\frac{n}{3})\ +\ 2T(\frac{n}{9})\ +\ n\ \leq\ 4T(\frac{n}{3})\ +\ n

Per il primo caso del teorema master vale

T(n) \leq O(n^{\log_3 4})

e quindi T(n) ha complessita' super-lineare
« Last Edit: 08-12-2010, 17:34:37 by shiny » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #5 on: 08-12-2010, 16:20:41 »

Quote
ti riferisci alla serie?
si
Quote
Per il primo caso del teorema master vale
ma non è nella forma per il teorema di master.
Dovresti applicare l'albero di ricorrenza!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 08-12-2010, 17:29:56 »

ma non è nella forma per il teorema di master.
Dovresti applicare l'albero di ricorrenza!

Scusa ma da quando
4T(\frac{n}{3})\ +\ n
non e' nella forma per il teorema master? o.O

Stai attento che ho fatto una maggiorazione per poterla ricondurre ad una facilmente risolvibile... l'unica pecca che posso trovare e' che magari non ho trovato il limite superiore stretto ma francamente mi seccavo
« Last Edit: 08-12-2010, 17:37:09 by shiny » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #7 on: 08-12-2010, 18:52:16 »

ma non è nella forma per il teorema di master.
Dovresti applicare l'albero di ricorrenza!

Scusa ma da quando
4T(\frac{n}{3})\ +\ n
non e' nella forma per il teorema master? o.O

Stai attento che ho fatto una maggiorazione per poterla ricondurre ad una facilmente risolvibile... l'unica pecca che posso trovare e' che magari non ho trovato il limite superiore stretto ma francamente mi seccavo


Mi sembra giusto come ragionamento.
Io mi stavo cimentando con l' albero di ricorsione.....non so se è corretto ma l' ho fatto così:

Link Immagine

Ora il problema è che non ho ben capito come fare a stabilire nell' altezza la base e l' argomento del logaritmo.

Ho supposto che h fosse \log_9(n)

E poi che il costo fosse sempre lineare per ogni livello...quindi alla fine non dovrei avere O(n\log(n)) ?
Altra domanda, quando si usa il metodo dell' albero di ricorsione non ho capito quando si passa all' uso di una serie come mai a volte ho:

\sum_{i=0}^{\log(n)} e altre volte sottraiamo un nodo e abbiamo \sum_{i=0}^{\log(n)-1}
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #8 on: 08-12-2010, 21:03:03 »

Quote
non e' nella forma per il teorema master? o.O

Stai attento che ho fatto una maggiorazione per poterla ricondurre ad una facilmente risolvibile...
premesso che non avevo notato maggiorazione. E mi riferivo alla ricorrenza originale (nella quale non si può subito usare Master).
Quote
l'unica pecca che posso trovare e' che magari non ho trovato il limite superiore stretto ma francamente mi seccavo
in quanto alla ricorrenza simile trovata. Io ci andrei un pò più cautamente. Non è sempre così semplice, abbiamo trovato la notazione O è vero, ma non \Theta. Il chè potrebbe non andarci bene sempre!
Io opterei comunque per l'albero.
Quote
non so se è corretto ma l' ho fatto così:
anche qui premetto che non faccio ricorrenze da una vita. Ma se la memoria non mi inganna (se sbaglia qualcuno mi corregga). Credo che il secondo livello sia 2*(\frac{1}{9}\frac{1}{9}\frac{1}{27}\frac{1}{27})2*(\frac{1}{27}\frac{1}{27}\frac{1}{81}\frac{1}{81}) = \frac{64}{81}n
quindi possiamo pensare che ogni livello costo (\frac{8}{9})^i n
poi calcoli la lunghezza dell'albero. Che è il primo ramo che arriva ad uno.
E allora fai la serie che ha come argomento il costo di ogni livello come indice la lunghezza dell'albero.
E risolvi la serie.

Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #9 on: 08-12-2010, 21:17:41 »

Quote
non e' nella forma per il teorema master? o.O

Stai attento che ho fatto una maggiorazione per poterla ricondurre ad una facilmente risolvibile...
premesso che non avevo notato maggiorazione. E mi riferivo alla ricorrenza originale (nella quale non si può subito usare Master).
Quote
l'unica pecca che posso trovare e' che magari non ho trovato il limite superiore stretto ma francamente mi seccavo
in quanto alla ricorrenza simile trovata. Io ci andrei un pò più cautamente. Non è sempre così semplice, abbiamo trovato la notazione O è vero, ma non \Theta. Il chè potrebbe non andarci bene sempre!
Io opterei comunque per l'albero.
Quote
non so se è corretto ma l' ho fatto così:
anche qui premetto che non faccio ricorrenze da una vita. Ma se la memoria non mi inganna (se sbaglia qualcuno mi corregga). Credo che il secondo livello sia 2*(\frac{1}{9}\frac{1}{9}\frac{1}{27}\frac{1}{27})2*(\frac{1}{27}\frac{1}{27}\frac{1}{81}\frac{1}{81}) = \frac{64}{81}n
quindi possiamo pensare che ogni livello costo (\frac{8}{9})^i n
poi calcoli la lunghezza dell'albero. Che è il primo ramo che arriva ad uno.
E allora fai la serie che ha come argomento il costo di ogni livello come indice la lunghezza dell'albero.
E risolvi la serie.




 testate

Si vero vero ho dimenticato che praticamente ogni chiamata è fatta due volte.
Forse volevi dire altezza dell' albero?
Ecco io non capisco come trovare la base e l'argomento del logaritmo che mi indica l 'altezza...tu hai detto che è data quando trovo 1?
Ma non capisco come trovarla.....
« Last Edit: 08-12-2010, 21:20:45 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #10 on: 08-12-2010, 21:29:02 »

Per sostituzione si dimostre che O(n) è accettata. 
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #11 on: 08-12-2010, 22:13:42 »

la base è il reciproco del moltiplicatore che sta nella ricorrenza (nel nostro caso sono \frac{1}{3} \ e \ \frac{1}{9} quindi 3 e 9 che arriva prima ad uno quindi è il ramo più alto - hai ragione non più lungo) mentre l'argomento è n.
Comunque alla fine la serie viene una geometrica di ragione \frac{8}{9}<1, quindi converge (a2, così la sommatoria viene 2n). E quindi il costo finale è \Theta (n).
Quote
Per sostituzione si dimostre che O(n) è accettata.
Sicuramente si può fare anche per sostituzione.
Ma trovi \Theta(n) \ o \ O(n) ??
« Last Edit: 08-12-2010, 22:15:45 by cock86 » Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #12 on: 09-12-2010, 09:10:16 »

la base è il reciproco del moltiplicatore che sta nella ricorrenza (nel nostro caso sono \frac{1}{3} \ e \ \frac{1}{9} quindi 3 e 9 che arriva prima ad uno quindi è il ramo più alto - hai ragione non più lungo) mentre l'argomento è n.
Comunque alla fine la serie viene una geometrica di ragione \frac{8}{9}<1, quindi converge (a2, così la sommatoria viene 2n). E quindi il costo finale è \Theta (n).
Quote
Per sostituzione si dimostre che O(n) è accettata.
Sicuramente si può fare anche per sostituzione.
Ma trovi \Theta(n) \ o \ O(n) ??

Solitamente per sostituzione si dimostra il limite asintotico superiore, però per dimostrare il limite stretto il passo è breve. Come hai ben detto tu, infatti, si può anche dimostrare che la soluzione è \Theta(n)
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #13 on: 09-12-2010, 15:54:23 »

la base è il reciproco del moltiplicatore che sta nella ricorrenza (nel nostro caso sono \frac{1}{3} \ e \ \frac{1}{9} quindi 3 e 9 che arriva prima ad uno quindi è il ramo più alto - hai ragione non più lungo) mentre l'argomento è n.
Comunque alla fine la serie viene una geometrica di ragione \frac{8}{9}<1, quindi converge (a2, così la sommatoria viene 2n). E quindi il costo finale è \Theta (n).
Quote
Per sostituzione si dimostre che O(n) è accettata.
Sicuramente si può fare anche per sostituzione.
Ma trovi \Theta(n) \ o \ O(n) ??
Per sostituzione trovi  O(n) (dimostrandolo per induzione).
Ma dal momento che il lavoro esterno è "n", è evidente che globalmente T(n)= \Theta(n)
Logged
Pages: [1]   Go Up
Print
Jump to: