algoritmi di ordinamento

[5t4rdu5t]

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]

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]

(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]

Supponendo che alla fine della seconda sommatoria ci sia un uno, quindi è questa roba:



distribuendo:



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:


(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:



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



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



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



allora è immediato che:



Per finire, dunque:



(se non ho sbagliato qualche conto )

[goatboy]

Ho sempre più paura di te, MItaly

[MItaly]

Non è che abbia fatto chissà che conti, è solo il LaTeX che li fa diventare più belli!

[goatboy]

Originariamente inviato da MItaly
Non è che abbia fatto chissà che conti, è solo il LaTeX che li fa diventare più belli!

E' la tua professionalità che è troppo cool
Sei il Chuck Norris della sezione Programmazione
Chiuso OT

[5t4rdu5t]

Originariamente inviato da MItaly
Supponendo che alla fine della seconda sommatoria ci sia un uno, quindi è questa roba:



distribuendo:



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]

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 )

[5t4rdu5t]

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



allora è immediato che:



Per finire, dunque:



(se non ho sbagliato qualche conto )

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:

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