| V I S U A L I Z Z A D I S C U S S I O N E |
| Shadow85 |
Inserito il - 14/09/2010 : 11:24:49
Qualcuno è riuscito a risolvere l'ultimo quesito o sa come si fa?
Allegato:  Scritto20100902.pdf
20,36 KB |
| 1 U L T I M E R I S P O S T E (in alto le più recenti) |
| ilblondo |
Inserito il - 26/09/2010 : 11:27:48
Premetto che non ho fatto lo scritto ma credo che si faccia così
Prendendo in considerazione l'operazione dominante
A[p1]<A[q1]
Sappiamo anche che è una funzione ricorsiva quindi dobbiamo prendere in considerazione una relazione di ricorrenza
Visto che l'operazione di fusione è proporzionale alla dimensione dell'array(n) la relazione di ricorrenza sarà
a n=1 a costante
f(n)=
2f(n/2)+cn n>1 c costante
se n è potenza di due la ricolviamo con sostituzioni successive quindi
n=2^k
f(n)=2(2f(n/4)+c(n/2))+cn ==
4f(n/4)+2cn==
4(2f(n/8)+c(n/4)+2cn== etc...
2^kf(1)+kcn=an+cn*log(n)(in base 2)
se 2^k<=n<=2^(k+1) ==> f(n)<=f(2^(k+1))
f(n) è un O(nlog(n)(in base 2))
anche nel caso pessimo la complessità è di nlog((n)inbase2)
si dovrebbe fare così....
|
