Forum Informatica Unict » LAUREA TRIENNALE (D.M. 270/04) » II anno » Algoritmi, 9 CFU (Moderator: Domenico Cantone) » Come risolvere questa ricorrenza? (compito di oggi 08/03)
Pages: [1] 2   Go Down
« precedente successivo »
Print
Author Topic: Come risolvere questa ricorrenza? (compito di oggi 08/03)  (Read 2210 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Edgarpoe
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 338


"Sorridi, domani sarà peggio"


WWW
« on: 08-03-2012, 19:22:19 »
T(n) = 3T(n/5) + T(n/2) + n


L'albero di ricorsione dovrebbe essere una cosa del genere:



                               n
                           /        \
                       /                \
                   /                        \
           3(n/5)                        n/2                           ->11/10n
          /         \                      /      \
3(n/25)        n/10        3(n10)     (n/4)                   ->77/100n


Sto sbagliando qualcosa? non mi riesce di stabilire una regola per il costo dell'iesimo livello.
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
Edgarpoe
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 338


"Sorridi, domani sarà peggio"


WWW
« Reply #1 on: 08-03-2012, 19:33:31 »
Ho trovato dove sbagliavo:



                               n
                           /        \
                       /                \
                   /                        \
           3(n/5)                        n/2                           ->11/10n
          /                               /      \
3[(n/25)  n/10]        3(n10)        (n/4)                   ->121/100n


Il costo è n(11/10)^i
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
**
Offline Offline

Posts: 114


Compila o non compila, questo è il problema!
« Reply #2 on: 08-03-2012, 19:35:56 »
Ciao, non riesci a stabilirla perché a profondità 2 hai 9(n/25)+6(n/10)+n/4=121/100 e quindi [(11/10)^i]n
Come soluzione ho messo O(n), seguendo i vari passaggi intermedi..

EDIT: Come non detto :-)
Logged
Flyer
Apprendista Forumista
**
Offline Offline

Posts: 100
« Reply #3 on: 08-03-2012, 19:38:14 »
Quote from: ExEcUtIvE on 08-03-2012, 19:35:56
Ciao, non riesci a stabilirla perché a profondità 2 hai 9(n/25)+6(n/10)+n/4=121/100 e quindi [(11/10)^i]n
Come soluzione ho messo O(n), seguendo i vari passaggi intermedi..

EDIT: Come non detto :-)
Potresti scrivere i passaggi che hai fatto? 
Logged
ExEcUtIvE
Apprendista Forumista
**
Offline Offline

Posts: 114


Compila o non compila, questo è il problema!
« Reply #4 on: 08-03-2012, 19:47:55 »
Quote from: Flyer on 08-03-2012, 19:38:14

Potresti scrivere i passaggi che hai fatto? 
Credo che ti interessa sapere maggiormente il punto in cui si capisce che è lineare...Svolgendoti la sommatoria come serie geometrica di ragione q>1, arrivi a calcolare (11/10)^(log(n)+1)=(11/10)*(11/10)^log(n)=(11/10)*(n)^log(11/10)
poiché log(11/10) è 0,(qualcosa) hai n^0 che è 1 quindi dalla sommatoria ottieni una costante che poi moltiplicata ad n che sta fuori dalla sommatoria ottieni una eq. di ricorrenza del tipo T(n)= n*(qualche costante)+n
Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..
Scusate se non ho utilizzato latex e se non ho scritto tutti i vari passaggi, ma vado molto di fretta..spero di esserti stato utile..
« Last Edit: 08-03-2012, 22:05:30 by ExEcUtIvE » Logged
Edgarpoe
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 338


"Sorridi, domani sarà peggio"


WWW
« Reply #5 on: 08-03-2012, 19:54:27 »
non vorrei aver preso un granchio, ma 11/10, essendo > di 1 non porta la serie a crescere indefinitamente?
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
**
Offline Offline

Posts: 114


Compila o non compila, questo è il problema!
« Reply #6 on: 08-03-2012, 19:55:49 »
Quote from: Edgarpoe on 08-03-2012, 19:54:27
non vorrei aver preso un granchio, ma 11/10, essendo > di 1 non porta la serie a crescere indefinitamente?
si scusa mi sono confuso un attimo il procedimento che ho fatto è per la serie con ragione >1 XD ...corretto!!
Logged
Edgarpoe
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 338


"Sorridi, domani sarà peggio"


WWW
« Reply #7 on: 08-03-2012, 20:15:19 »
Quote from: ExEcUtIvE on 08-03-2012, 19:47:55
Quote from: Flyer on 08-03-2012, 19:38:14

Potresti scrivere i passaggi che hai fatto?  
Credo ti interessa sapere maggiormente il punto in cui si capisce che è lineare...Svolgendoti la sommatoria come serie geometrica di ragione q>1, arrivi a calcolare (11/10)^(log(n)+1)=(11/10)*(11/10)^log(n)=(11/10)*(n)^log(11/10)
poiché log(11/10) è 0,(qualcosa) hai n^0 che è 1 quindi dalla sommatoria ottieni una costante che poi moltiplicata ad n che sta fuori dalla sommatoria ottieni una eq. di ricorrenza del tipo T(n)= n*(qualche costante)+n
Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..
Scusate se non ho utilizzato latex e se non ho scritto tutti i vari passaggi, ma vado molto di fretta..spero di esserti stato utile..


E' la parte in grassetto a non essermi chiara, se qualcuno vorrà aiutarmi gliene sarò infinitamente grato
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
**
Offline Offline

Posts: 114


Compila o non compila, questo è il problema!
« Reply #8 on: 08-03-2012, 21:45:05 »
Quote from: Edgarpoe on 08-03-2012, 20:15:19
E' la parte in grassetto a non essermi chiara, se qualcuno vorrà aiutarmi gliene sarò infinitamente grato
ecco qui quella parte, scritta bene..è lo svolgimento della serie..
http://www.image-share.com/ijpg-1338-66.html
non l'ho svolta tutta, però questo è il pezzo più "complesso"..
« Last Edit: 08-03-2012, 21:47:33 by ExEcUtIvE » Logged
Edgarpoe
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 338


"Sorridi, domani sarà peggio"


WWW
« Reply #9 on: 08-03-2012, 21:52:36 »
Grazie davvero 
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
**
Offline Offline

Posts: 114


Compila o non compila, questo è il problema!
« Reply #10 on: 08-03-2012, 22:37:11 »
Quote from: Edgarpoe on 08-03-2012, 21:52:36
Grazie davvero 
Figurati, se non ci si aiuta tra colleghi...  ;-)
Logged
chernobyl
Matricola
*
Offline Offline

Gender: Male
Posts: 79
« Reply #11 on: 09-03-2012, 10:46:01 »
Ragazzi ma allora la risposta esatta è O(n)?
Logged
eLis
Apprendista Forumista
**
Offline Offline

Gender: Female
Posts: 111
« Reply #12 on: 09-03-2012, 10:50:01 »
No la risposta è O(n^2). La sommatoria dà O(n) ma questa è moltiplicata per n
Logged
The Man in Black fled across the desert, and the Gunslinger followed.
chernobyl
Matricola
*
Offline Offline

Gender: Male
Posts: 79
« Reply #13 on: 09-03-2012, 10:51:51 »
allora ho risposto giusto!
Logged
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 601
« Reply #14 on: 09-03-2012, 17:51:03 »
Quote from: eLis on 09-03-2012, 10:50:01
No la risposta è O(n^2). La sommatoria dà O(n) ma questa è moltiplicata per n
Ok, finalmente qualcuno che corregge 
Logged
Pages: [1] 2   Go Up
Print
« precedente successivo »
Jump to: