DOMANDA Sort / complessita'

[MPG]

Scusate per un selection sort pensavo a questo algoritmo:

#include<iostream>
using namespace std;

main()
{
    int a[10]={5,8,0,1,4,2,4,3,9,7};
    int i,j,min,temp;

    for(i=0; i<9; i++)                      
{
        min=i;                                      
        for (j=i+1;j<10;j++)           
         {   if (a[j]<a[min])              
              min=j;                              
           }
        temp = a[min];                  
        a[min] = a[i];                   
        a[i] = temp;                      
  }

for(int i=0;i<10;i++)
        cout<<a[i]<<" ";
}

Ho sempre dubbi sui passi base e sulla complessità nel caso peggiore, medio e migliore?

Ω (migliore)

θ(medio)

O (peggiore)

Mi potete aiutare?

Grazie a tutti.

ps

Ho provato mi verrebbe:
1+ n +(n-1)[1+1+n*(n-1) (1+1+1+1+1+1+1)
esattamente
i=0 1
i<9 n
i++ n-1
min=i 1
j=i+1 1
j<10 n
j++ n-1
if (a[j]<a[min]) (n-1)
min=j; (n-1)
}
temp = a[min]; (n-1)
a[min] = a; (n-1)
a = temp; (n-1)
}

 

[BAT]

Ω = servono almeno (cioò non meno di) un certo numero di passi (delimitazione inferiore)
O = servono al più un certo numero di passi (limite superiore)
θ = la notazione "teta" indica che servono esattamente un certo numero di passi, un concetto completamente differente da "media"
Per selectionsort l'algoritmo prevede la ricerca del minimo (o del massimo) in un vettore di n elementi per cui esegui al peggio n^2 confronti;
Ω = n^2, O = n^2, di conseguenza θ = n^2

Come confronto, il quicksort ha complessità asintotica O(n^2) tuttavia, a differenza di selection/bubble/altri-sort (eccetto mergesort) è piuttosto efficiene e, nel caso medio (e con un po' di fortuna), la complessità è circa O(n*log2(n)) (log2 = logaritmo in base 2), come il mergesort che sulla carta è il migliore con la sua θ(n*log2(n)).
Ci sarebbe parecchio da discutere su cosa si intende per "caso medio" ed in che modo viene stabilito, ma sono argomenti da corsi universitari (e certe volte neanche di quelli: i prof. spesso si limitano a dire "nel caso medio..." senza approfondire la cosa).

 

[MPG]

Si ma devo capire perchè si arriva a 0(n^2) presumendo che dovrei prima fare il conto dei passi base.
Su appunti ch eho se ad esempio il numero passi base risulta n^2+2n+2 la complessita' asintotica è n^2 , in pratica è definita dal blocco di complessità maggiore, ma qui devo capire bene il conto dei passi base anche nel mio algoritmo... Inoltre perchè qui la complessità asintotica di Ω , O e θ è sempre uguale a n^2 ?

Ho provato a fare dei conti ho aggiornato come vi sembra?

 

[BAT]

metti che devi ordinare in ordine crescente e che ad ogni passo cerchi il minimo
punti l'indice sul primo elemento
alla prima passata selectionsort fa n-1 confronti poi, trovato il minimo, lo scambia col primo elemento (1 scambio)
sposti inavanti l'indice di una posizione, e al secondo passo fai n-2 confronti, riesegui lo scambio e continui
...fino al penultimo elemento (quando ne rimane uno solo non c'è nulla da confrontare).
alla fine hai fatto (n-1)+(n-2)+...+1 = 1+2+...+(n-2)+(n-1) = n*(n-1)/2 confronti e (n-1) scambi

 

[MPG]

metti che devi ordinare in ordine crescente e che ad ogni passo cerchi il minimo
punti l'indice sul primo elemento
alla prima passata selectionsort fa n-1 confronti poi, trovato il minimo, lo scambia col primo elemento (1 scambio)
sposti inavanti l'indice di una posizione, e al secondo passo fai n-2 confronti, riesegui lo scambio e continui
...fino al penultimo elemento (quando ne rimane uno solo non c'è nulla da confrontare).
alla fine hai fatto (n-1)+(n-2)+...+1 = 1+2+...+(n-2)+(n-1) = n*(n-1)/2 confronti e (n-1) scambi

SCusa ma non capisco, sono abituato ad esaminare uno ad uno gli elementi come ho fatto sopra......
Allego esempi che devo seguire guarda il numero 4.
--- i due messaggi sono stati uniti ---

metti che devi ordinare in ordine crescente e che ad ogni passo cerchi il minimo
punti l'indice sul primo elemento
alla prima passata selectionsort fa n-1 confronti poi, trovato il minimo, lo scambia col primo elemento (1 scambio)
sposti inavanti l'indice di una posizione, e al secondo passo fai n-2 confronti, riesegui lo scambio e continui
...fino al penultimo elemento (quando ne rimane uno solo non c'è nulla da confrontare).
alla fine hai fatto (n-1)+(n-2)+...+1 = 1+2+...+(n-2)+(n-1) = n*(n-1)/2 confronti e (n-1) scambi

Nn capisco ..
mettiamo 5 numeri
(n-1)+(n-2)+(n-3) + (n-4) sono i confronti
1+1+1 +1 gli scambi?
e' giusto?
Ma perchè poi quel =n(n-1)/2 ?
e n-1 scambi??

 

[fabio93]

Per capire la complessità dell'algoritmo devi ragionare sul suo funzionamento.
Il selection sort funziona in questo modo (in caso di un ordinamento crescente): alla prima iterazione, viene selezionato l'elemento più piccolo dell'array, e scambiato con il primo elemento. Alla seconda iterazione, viene selezionato il secondo elemento più piccolo, e scambiato con il secondo elemento. L'algoritmo procede così finché all'ultima iterazione viene selezionato il secondo elemento più grande (cioè il penultimo più piccolo) e scambiato con il penultimo elemento, lasciando l'elemento più grande in ultima posizione. Pertanto, dopo i iterazioni, i più piccoli i elementi saranno ordinati nelle prime i posizioni dell'array.
Il ciclo esterno itera sui primi n-1 elementi (tutti tranne l'ultimo), e si occupa di scambiare l'elemento di volta in volta considerato con il minimo corrente, trovato dal ciclo interno. Il ciclo interno, dal canto suo, itera su tutti gli elementi della porzione non ancora ordinata dell'array. Quindi, alla prima iterazione del ciclo esterno, il ciclo interno viene eseguito n-1 volte (cioè itera dal secondo all'ultimo elemento), alla seconda iterazione, n-2 volte (dal terzo all'ultimo elemento), poi n-3, ... , 3, 2, 1 volte. Come ha scritto @BAT00cent, sommando questi numeri si ottiene la serie numerica (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = n(n-1)/2 = (n^2-n)/2 che, nella notazione "O grande", corrisponde a O(n^2).

Volendo calcolare la complessità statement per statement, devi tenere presente che, per quanto riguarda il costrutto for (j=i+1;j<n;j++), i=i+1 viene eseguito ovviamente una volta, j<n viene eseguito n-(i+1)+1 = n-i-1+1 = n-i volte, e infine j++ viene eseguito n-(i+1) = n-i-1 volte.
Perciò, assumendo che la condizione dell'if sia sempre vera, si ottiene

1 + n + n-1 + (n-1)(1 + 1 + n-i + n-i-1 + (n-i-1)(1+1) + 1 + 1 + 1) =
2n + (n-1)(2(n-i) + 1 + 2(n-i-1) + 3) =
2n + (n-1)(2(n-i) + 2(n-i-1) + 4) =
2n + (n-1)(2n-2i + 2n-2i-2 + 4) =
2n + (n-1)(4n-4i+2) =
2n + 4n^2 - 4ni + 2n - 4n + 4i - 2 =
4n^2 - 4ni + 4i - 2 = 4n^2 + i(4 - 4n) - 2 = O(4n^2) = O(n^2)

 

[MPG]

IO non capisco
1) se somma (n-1)+(n-2)+ (n-3)+(n-4)= 4n-10
quindi perchè n(n-1)/2 ??
2)non capisco" j<n viene eseguito n-(i+1)+1 = n-i-1+1 = n-i volte,"
abbiamo sempre usato a lezione n e numero non inserimento di i , è l'unico metodo?
In ogni caso mi sto spremendo e non capisco perchè n-(i+i)+1, cosa signifcherebbe?
3) perchè (n^2-n)/2 nelle notazione O grande corrisponde a O(n^2)?
Grazie del supporto.

 

[rodhellas]

IO non capisco
1) se somma (n-1)+(n-2)+ (n-3)+(n-4)= 4n-10
quindi perchè n(n-1)/2 ??
2)non capisco" j<n viene eseguito n-(i+1)+1 = n-i-1+1 = n-i volte,"
abbiamo sempre usato a lezione n e numero non inserimento di i , è l'unico metodo?
In ogni caso mi sto spremendo e non capisco perchè n-(i+i)+1, cosa signifcherebbe?
3) perchè (n^2-n)/2 nelle notazione O grande corrisponde a O(n^2)?
Grazie del supporto.

1) n(n+1)/2 è la formula per trovare la somma dei primi n numeri (a partire da 1, quindi se parti da 0, sostituisci n-1 a n e ritrovi la formula detta dal buon BAT0). Essendo la somma dei vari confronti (che ad ogni iterazione decrescono), puoi usare n(n-1)/2. Se sostituisci n = 4, 4n-10 e n(n-1)/2 danno entrambi 6.
2) n-i volte perchè non parti da 0 ma da i+1.
3) Perchè per n tendente a valori grandi, l'elemento che darà più peso sarà n^2. Ovvero avrà una complessità nell'ordine di n^2.

 

[fabio93]

Aggiungo che il fatto che la somma n + (n-1) + ... + 2 + 1 è uguale a n(n+1)/2, è un risultato matematico molto noto, scoperto da Gauss (prende il nome di formula di Gauss, qui trovi una spiegazione). Si può dimostrare con il principio di induzione.

 

[MPG]

1) n(n+1)/2 è la formula per trovare la somma dei primi n numeri (a partire da 1, quindi se parti da 0, sostituisci n-1 a n e ritrovi la formula detta dal buon BAT0). Essendo la somma dei vari confronti (che ad ogni iterazione decrescono), puoi usare n(n-1)/2. Se sostituisci n = 4, 4n-10 e n(n-1)/2 danno entrambi 6.
2) n-i volte perchè non parti da 0 ma da i+1.
3) Perchè per n tendente a valori grandi, l'elemento che darà più peso sarà n^2. Ovvero avrà una complessità nell'ordine di n^2.

Hai scritto n(n+1)/2 e mi dici che essendo la somma di vari confronti si puo' usare n(n-1)/2on ho scusami ma sai siete ad un altro livello dle mio molto piu' basso...
INoltre nel link dato dal prof:

Time Complexities of all Sorting Algorithms - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Algorithm	Time Complexity
	Best	Average	Worst
Selection Sort	Ω(n^2)	θ(n^2)	O(n^2)

mentre in allegato trovo diverso il best O(n) per selection sort, errato?
Mi puoi confermare best, average e worst?
IN pratica se mi viene chiesto dal prof di spiegare la complessità nel caso migliore, medio, peggiore.
Dovrei dire quello che ha scritto BAt?
"
Ω = servono almeno (cioò non meno di) un certo numero di passi (delimitazione inferiore)
O = servono al più un certo numero di passi (limite superiore)
θ = la notazione "teta" indica che servono esattamente un certo numero di passi, un concetto completamente differente da "media"
Per selectionsort l'algoritmo prevede la ricerca del minimo (o del massimo) in un vettore di n elementi per cui esegui al peggio n^2 confronti;
Ω = n^2, O = n^2, di conseguenza θ = n^2
"
Ma in pratica , terra terra, il caso peggiore e' come quello migliore perchè l'array va esaminato tutto per cui sono tot cofronti che vanno fatti e che sono sempre n^2 o c'è qualcosa che non riesco a capire veramente?

 

[rodhellas]

Hai scritto n(n+1)/2 e mi dici che essendo la somma di vari confronti si puo' usare n(n-1)/2

n(n+1)/2 è da 1 a n, ma nel tuo caso, inizi da 0 fino a n-1 (cioè sposta tutto indietro di 1). Sostituisci n-1 a n e ottieni (n-1)(n-1+1)/2, ovvero n(n-1)/2.
Guarda che nell'allegato hai guardato la riga sbagliata, selectionSort è sempre O(n^2)..

Ma in pratica , terra terra, il caso peggiore e come quello migliore perchè l'array va esaminato tutto per cui sino tot cofrontiche vanno fatti e che sono sempre n^2 o c'è qualcosa che non riesco a capire veramente?

Occhio che vale solo nel selectionSort! In altri algoritmi non è detto che siano uguali (e menomale!).

 

[MPG]

NOn voglio mettere troppa carne al fuoco ma cerco di capire bene tutto
Ho trovato in altra fonte:
"
Per realizzare l’algoritmo di ordinamento utilizziamo allora un ciclo esterno con un indice i che va da 0 ad n-2.
Dopo utilizziamo la variabile min che memorizza l’indice a cui punta il valore minimo. Questa variabile è inizializzata al primo elemento: min=i.
Poi realizziamo un ciclo interno utilizzando un indice j che va da i+1 (posizione successiva ad i) fino ad n.
Infine controlliamo se il numero puntato dall’indice j è più piccolo del min e se è vero lo scambiamo. Per effettuare lo scambio utilizzo una variabile temporanea temp.
"
Per quella parte che dice da 0 a n-2 viene ribadita anche in allegato di una dispensa perchè?
Non va da 0 a n-1??

 

[rodhellas]

Per quella parte che dice da 0 a n-2 viene ribadita anche in allegato di una dispensa perchè?
Non va da 0 a n-1??

Ma scusa, hai letto l'allegato che hai aggiunto? L'ultimo elemento non lo si controlla perchè alla fine dei vari cicli sarà automaticamente al posto giusto.

 

[fabio93]

Per quella parte che dice da 0 a n-2 viene ribadita anche in allegato di una dispensa perchè?
Non va da 0 a n-1??

Il ciclo esterno itera su tutti gli elementi tranne l'ultimo, vale a dire da quello di indice 0 (il primo) a quello di indice n-2 (il penultimo).
Questo si può esprimere con la condizione i < n-1 (come hai fatto nel tuo codice) o i <= n-2, sono la stessa cosa. L'elemento n-1-esimo come vedi non viene scandito.

 

[BAT]

Giusto per farti un esempio pratico, la formula di Gauss serve a sommare i primi N numero a partire da 1 cioè la somma
1+2+3+...+N=N*(N+1)/2
esempio con N=100 --> 1+2+3+...+100= 100*(100+1)/2 = 5050
quindi se sommi K=N-1 numeri la formula diventa
1+2+3...+K = K*(K+1)/2 = sostituendo K = (N-1)*(N-1+1)/2=(N-1)*N/2=N*(N-1)/2
il termine più alto è N^2 e quindi l'algoritmo è O(N^2)