Forum by laureateci.it

Tutti i Forum

Nota: Devi essere registrato per poter inserire un messaggio.
Per registrarti, clicca qui. La Registrazione è semplice e gratuita!

Larghezza finestra:

Nome Utente:

Password:

Modo:

Formato:

Icona Messaggio:

Messaggio:

* Il codice HTML è OFF
* Il Codice Forum è ON

Smilies

Allega file

Clicca qui per inserire la tua firma nel messaggio.
Clicca qui per sottoscrivere questa Discussione.

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ì....

Forum by laureateci.it

Il DB ha risposto in 0,05 secondi.