PDA

Visualizza la versione completa : algoritmi di ordinamento


5t4rdu5t
19-07-2012, 16:15
ragazzi scusate ma nn sto capendo una cosa la complessità basata sui confronti dell algoritmo selectionsort si scrive sommatoria che da i a n-2 che moltiplica tra parentesi 1+sommatoria j=i+1 a n-1, e tutto questo è uguale a (n-1)+sommatoria da i = 0 a n-2 che moltiplica (n-i-1). Qualcuno può spiegarmi questo passaggio? vi saeri infinitamente grato grazi e scusate se ho scritto così nn so usare latex

MItaly
19-07-2012, 16:35
Originariamente inviato da 5t4rdu5t
sommatoria che da i a n-2 che moltiplica tra parentesi 1+sommatoria j=i+1 a n-1
Il primo i da cosa parte? Quest'ultima sommatoria cos'ha dentro?

5t4rdu5t
19-07-2012, 16:53
(E che va da i = 0, a n-2)*(1+ E che va da j=i+1, a n-1) = (n-1)+E che va da i = 0, a n-2 *(n-i-1), speso si capisca meglio

MItaly
19-07-2012, 17:19
Supponendo che alla fine della seconda sommatoria ci sia un uno, quindi è questa roba:

http://bit.ly/Mub9BO

distribuendo:

http://bit.ly/NUbLys

A questo punto, tutto è ridotto a sommatorie di uni; ora, una sommatoria di uni equivale a contare uno per tutti i valori che assume il suo indice, ovvero:

http://bit.ly/LuXeJn
(il +1 è necessario perché la sommatoria itera su tutti i numeri da m a M, estremi compresi); sostituendo quindi questa relazione nella precedente, si ottiene:

http://bit.ly/LYVvlK

ora consideriamo il termine in sommatoria: si può distribuire anche questo; si ha:

http://bit.ly/Muc993

Dato che n-1 è indipendente da i, si può portare fuori, e riapplicando la regola di prima si ottiene:

http://bit.ly/PmgDRC

Per quanto riguarda il secondo pezzo, basta ricordare il teorema (si dimostra facilmente per induzione) per cui

http://bit.ly/QbXTFR

allora è immediato che:

http://bit.ly/Lv1EQo

Per finire, dunque:

http://bit.ly/P80ax1

(se non ho sbagliato qualche conto :stordita: )

goatboy
19-07-2012, 22:47
Ho sempre più paura di te, MItaly :spy:
:D

MItaly
20-07-2012, 00:42
Non è che abbia fatto chissà che conti, è solo il LaTeX che li fa diventare più belli! :stordita:

goatboy
20-07-2012, 08:32
Originariamente inviato da MItaly
Non è che abbia fatto chissà che conti, è solo il LaTeX che li fa diventare più belli! :stordita:
E' la tua professionalità che è troppo cool :D
Sei il Chuck Norris della sezione Programmazione :fighet:
Chiuso OT :madai!?:

5t4rdu5t
20-07-2012, 14:56
Originariamente inviato da MItaly
Supponendo che alla fine della seconda sommatoria ci sia un uno, quindi è questa roba:

http://bit.ly/Mub9BO

distribuendo:

http://bit.ly/NUbLys

A questo punto, tutto è ridotto a sommatorie di uni; ora, una sommatoria di uni equivale a contare uno per tutti i valori che assume il suo indice...

intanto grx per la disponibilità non ho capito bene questa parte se il primo ciclo svolge l' istruzione di controllo n-1 per fare if (data[j] < data[least]) least = j; e il secondo ciclo lo svolge n-i-1 volte perchè abbiamo tre sommatorie? innoltre l' 1 sta per una costante? a che fare cn lo swap??

MItaly
20-07-2012, 15:26
Sì, ho preso come costante del tempo di scambio 1 (dato che non l'hai mai specificata). Comunque, posta la tua implementazione di riferimento, che vediamo da dove vengono fuori tutti i pezzi.

(e per cortesia evita il linguaggio da SMS :nonlodire )

5t4rdu5t
20-07-2012, 15:48
si scusami xD.. il codice che uso come riferimento è:


public void selectionsort(int[] data) {
int i,j,least;
for (i = 0; i < data.length-1; i++) {
for (j=i+1, least=i; j<data.length; j++)
if (data[j] < data[least])
least = j;
if (least != i)
swap(data,least,i);
}
}



invece questa parte non capisco quando dici:


Originariamente inviato da MItaly

Per quanto riguarda il secondo pezzo, basta ricordare il teorema (si dimostra facilmente per induzione) per cui

http://bit.ly/QbXTFR

allora è immediato che:

http://bit.ly/Lv1EQo

Per finire, dunque:

http://bit.ly/P80ax1

(se non ho sbagliato qualche conto :stordita: )

il secondo pesso sarebbe? la sommatoria con la i? xD

guardando i passaggi mi è venuto un dubbio.. non sn sicuro ma... potrebbe macare un n qua:


Originariamente inviato da MItaly

Per finire, dunque:

http://bit.ly/P80ax1


in modo da venire (n-1)+(n(n-1))/2 = O(n^2)

Loading