Pages: [1]   Go Down
Print
Author Topic: T(n) = 2T(n-1)+n  (Read 2293 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Root
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 474



« on: 27-04-2009, 18:49:17 »

Salve, oggi svolgendo il compito del 19-02 B mi sono imbatutto in questa equazione di ricorrenza:

T(n) = 2T(n-1)+n

mi sono detto... ora la risolvo per sostituzione! (Cormen paragrafo 4.1)
Ho svolto così:

Link Immagine

Ora, cosa ho sbagliato? Il bound da me scelto è il più largo tra quelli proposti dal prof... qualcuno mi sa dire che sta succedendo?

Grazie
Dario
Logged

Passa a jabber!
http://jabber.org (il servizio)
http://pidgin.im (il client)

(c'era una volta) www.mytwocent.it
Condividi le tue conoscenze!

linux registered user #449678
Yngwie
Forumista
***
Offline Offline

Gender: Male
Posts: 849


Maestro! mi dia un MI in chiave di SOL!


« Reply #1 on: 27-04-2009, 19:09:24 »

qualcuno mi sa dire che sta succedendo?
semplice: studiare algoritmi nuoce gravemente alla salute testate I univ

ps: hai tutti i testi degli appelli passati?
Logged

Root
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 474



« Reply #2 on: 27-04-2009, 21:44:40 »

http://www.mytwocent.it/varie/cmptalg.zip
Logged

Passa a jabber!
http://jabber.org (il servizio)
http://pidgin.im (il client)

(c'era una volta) www.mytwocent.it
Condividi le tue conoscenze!

linux registered user #449678
Nova
Forumista
***
Offline Offline

Gender: Male
Posts: 567


-.-"


WWW
« Reply #3 on: 28-04-2009, 17:35:23 »

Dear Dario:

Io ho provato a risolvere per induzione questa eq. di ricorrenza ma mi blocco quasi alla fine:

T(n) <= 2[c(2^n-1)]+n
         = c2^n + n

In poche parole mi resta sempre quel termine n alla fine, se non fosse per quello mi risulterebbe che T(n)=2T(n-1)+n=O(2^n)
Logged

Ubuntu user:
#29872
Root
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 474



« Reply #4 on: 28-04-2009, 17:37:38 »

Ed è proprio quello il problema... mi sorge il dubbio che tra le soluzioni elencate non vi sia quella corretta

:S
Dario
Logged

Passa a jabber!
http://jabber.org (il servizio)
http://pidgin.im (il client)

(c'era una volta) www.mytwocent.it
Condividi le tue conoscenze!

linux registered user #449678
Nova
Forumista
***
Offline Offline

Gender: Male
Posts: 567


-.-"


WWW
« Reply #5 on: 28-04-2009, 17:44:58 »

Beh guarda, io le ho fatte tutte col metodo di induzione e nessuna mi risulta. io sono però ABBASTANZA (quasi tanto XD) scadente in questo ambito :p
Logged

Ubuntu user:
#29872
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


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


« Reply #6 on: 28-04-2009, 21:22:09 »

Con il metodo dell'albero di ricorsione mi viene . Può darsi che ci sia qualche errore domani ci provo a farlo
« Last Edit: 28-04-2009, 21:35:50 by Pandemia000 » Logged

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

Gender: Male
Posts: 849


Maestro! mi dia un MI in chiave di SOL!


« Reply #7 on: 28-04-2009, 22:12:56 »

la soluzione è O(2n), considerando che la ricorrenza è simile a quella del problema della torre di Hanoi...la dimostrazione a domani  testate pc
Logged

LtWorf
Forumista Esperto
****
Offline Offline

Posts: 1.079

Ogni cosa da me scritta è da intendersi come opinione personale e non come dato di fatto. Anche le eventuali dimostrazioni matematiche da me scritte saranno opinioni personali e quindi dovranno venire dimostrate da una terza parte di fiducia


WWW
« Reply #8 on: 05-05-2009, 19:39:43 »

Domani è passato...
Logged

There are some OO programming languages. I will create the first -_-' language.

LtWorf
Yngwie
Forumista
***
Offline Offline

Gender: Male
Posts: 849


Maestro! mi dia un MI in chiave di SOL!


« Reply #9 on: 05-05-2009, 19:40:23 »

appunto...niente dimostrazione nono
Logged

Pages: [1]   Go Up
Print
Jump to: