Forum by laureateci.it - Scritto 02-09-2010

Nome Utente:	Password:
Salva Password
Password Dimenticata?

Tutti i Forum

ITPS - Secondo Anno

Algoritmi e Strutture Dati + Lab.

Scritto 02-09-2010

Nuova Discussione

Nuovo Sondaggio

Rispondi

Versione Stampabile

Aggiungi Segnalibro

Autore

Discussione

Shadow85
Nuovo Utente

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

ilblondo
Utente giovane

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

--------------------------------------------------------------------------------------
Esistono 10 tipi di persone: quelle che conoscono il binario e quelle che non lo conoscono

Discussione

Nuova Discussione

Nuovo Sondaggio

Rispondi

Versione Stampabile

Aggiungi Segnalibro

Vai a:

Forum by laureateci.it

Il DB ha risposto in 0,17 secondi.