Pages: 1 [2]   Go Down
Print
Author Topic: Aiuto esercizi  (Read 3054 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #15 on: 15-09-2011, 13:13:13 »

Purtroppo non è così. shiny ha molta più esperienza di noi in materia, mi ha aiutato molto per questo esame. 
Il nostro è il secondo caso generalizzato del teorema Master.

f(n)=\theta(n^{\log_b(a)}*\log_b(n)^k) con k\geq 0

Che mi sembra funzioni alla grande.

Adesso si che le cose cambiano. Grazie, aggiungero' questa clausola nei miei appunti.
(mi sembra strano che sulle slide non ci sia, e che sul Cormen sia ben nascosta :/ )
Infatti il prof a lezione spiega il secondo caso generalizzato e non quello del Cormen e all'orale vuole essere ripetuto quello generalizzato se ti chiede il T.M.
Logged

Diventa ciò che sei nato per essere
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #16 on: 15-09-2011, 13:30:26 »


Il secondo caso del teorema master si applica:
-Se  f(n) = \Theta( n^{log_b(a)}) , cioe'
 f(n) = \Theta( n^{log_5(5)})
 f(n) = \Theta( n^1)

ma noi abbiamo:

 nlogn = \Theta( n) . che e' falso!
Qui trovi il teorema master e per k=1 hai che n\log n = \Theta(n\log n) e quindi la T(n)=\Theta(n\log^2n) 
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #17 on: 15-09-2011, 13:37:28 »

Quote
(mi sembra strano che sulle slide non ci sia

C' è....c'è......http://www.dmi.unict.it/~cutello/ricorrenza.pdf
Pag. 32.
Logged

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

Posts: 810



WWW
« Reply #18 on: 15-09-2011, 13:52:31 »

In quelle slides pero' la scrittura e' fuorviante in quanto n \log(n^k)\ \neq\ n \log^k(n)
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #19 on: 15-09-2011, 14:09:48 »

Ah ecco, lo avevo pensato pure io.....
Logged

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

Posts: 430


CЯΣDΣЯCI SΣMPЯΣ, ΛЯЯΣПDΣЯSI MΛI!


« Reply #20 on: 15-09-2011, 17:39:44 »

Grazie a tutti per la risposta!!!  ok
Logged

...๔єςเ, ๔єςเ, ๔єςเ...
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #21 on: 15-09-2011, 22:26:38 »

In quelle slides pero' la scrittura e' fuorviante in quanto n \log(n^k)\ \neq\ n \log^k(n)
E' vero la notazione è infelice, o meglio, ho scordato le parentesi. 
Logged
Pages: 1 [2]   Go Up
Print
Jump to: