Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Daréios89 on 22-11-2010, 20:55:43



Title: BucketSort
Post by: Daréios89 on 22-11-2010, 20:55:43
Non ho ben capito quando viene dimostrata l'equazione di ricorrenza:

T(n)=\theta(n)+\sum_{i=0}^{n-1}O(n_i^2)

Si arriva a:

E[\sum_{j=1}^{n}\sum_{k=1}^{n}X_i_jX_i_k ]

Non capisco il passaggio successivo....cioè come si arriva o meglio perchè si ha poi:

E[\sum_{j=1}^{n}X^2_i_j +\sum_{1\leq j\leq n}\sum_{1\leq k\leq n}X_i_jX_i_k] ?

Scusate ma il latex non sa fare di meglio  :pray


Title: Re:BucketSort
Post by: alex180788 on 15-12-2010, 10:24:50
tu hai scritto...
E[\sum_{j=1}^{n}\sum_{k=1}^{n}X_i_jX_i_k ]

attento, nei miei appunti questo è una somma e non due sommatorie annidate.... dovrebbe essere una proprietà della funzione valore atteso E[] c'è un'appendice apposta verso la fine del libro