[Algo] SelectionSort stabile e analisi
L'algoritmo è il seguente:
La complessità è un $O(n^2)$
Dato che ho $T(n) = O(n)*(O(n)+O(n)) = O(n^2)$
SelectionSort( A )
n = len(A)
for ( j=0 ; j<=n-2 ; j++)
min = Min( A, j )
Insert( A, j, min )
Min( A, j )
min = A[j]
for ( k= j+1 ; k<len(A) ; k++ )
if ( A[k] < min ) thena min=A[k]
return min
Insert( A, j, m)
x = A[m]
for ( k=m ; k>j ; k-- )
A[k] = A[k-1]
A[j] = x
La complessità è un $O(n^2)$
Dato che ho $T(n) = O(n)*(O(n)+O(n)) = O(n^2)$
Risposte
Scusa, ma qual è la domanda?
Si chiedo scusa. Il Selection Sort cosí implementato é sempre un $O(n^2)$ ?
Si, risulta sempre $O(n^2)$ in ogni caso. Facciamo l'analisi in tre passi
Iniziando dalla funzione generale, non ci sono possibili scelte o altre variazioni, per cui caso migliore medio e peggiore sono uguali:
n = len(A) $\rightarrow c_{1}$
for ( j=0 ; j<=n-2 ; j++) $\rightarrow (n-2)(c_{2} + c_{3})$
min = Min( A, j ) $\rightarrow (n-2)T(m)$
Insert( A, j, min ) $\rightarrow (n-2)T(i)$
da cui
$T(S) = c_{1} + (n-2)(c_{2} + c_{3}) + (n-2)T(m) + (n-2)T(i) $
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + T(m) + T(i))$
dove $c_{1}$ è il tempo di assegnamento e calcolo della lunghezza dell'array $A$ (in teoria sarebbe $O(n)$, ma supponiamo di averlo come dato memorizzato durante la costruzione dell'array). $c_{2}$ e $c_{3}$ sono i tempi di controllo del flag ($j \leq (n-2)$ e dell'incremento unitario $j++$, che possiamo pensare costanti. Dobbiamo valutare $T(m)$ e $T(i)$, tempi delle due funzioni Min() e Insert() . Queste avranno a prescindere dei tempi migliori, medi e peggiori diversi, dato che dipendono da parametri in ingresso, ma in realtà dato che vengono richiamate sia con valori tali da ottenere i tempi migliori che con valori tali da ottenere i tempi peggiori (in quanto il for scorre per forza tutti i valori su $j$), non bisogna spezzare il calcolo del tempo nei vari casi.
Per Min() , il caso peggiore si ha con $j = 0$, in quanto deve scorrere per forza tutto l'array per trovare il minimo. il migliore si ha con $j = l(A)-1 = n-1$, dato che trova il minimo immediatamente. Mediamente (ovvero con $j$ generico tra $0$ e $n-1$) otteniamo
min = A[j] $\rightarrow c_{1}$
for ( k= j+1 ; k
min=A[k] $\rightarrow K*c_{1})$
return min $ c_{4}$
dove $c_{1}$ è il costo di un assegnamento di intero, $c_{2}$ è il costo del controllo della condizione $k
Il termine $K$ è il numero di IF positivi, ovvero quante volte viene aggiornato il valore minimo. Il caso migliore ($K=0$) si ha quando il minimo risulta il primo valore considerato $A[j]$, e quindi non ci sono aggiornamenti. Il caso peggiore ($K=n-j$) si ha invece se l'array è ordinato in ordine decrescente (e quindi il minimo è l'ultimo valore).
$T(m) = c_{1} + (n-j)(c_{2}+c_{3}) + (n-j)*c_{2} + K*c_{1} = (K+1)*c_{1} + (n-j)(2c_{2}+c_{3})$
Siccome $K \in [0, n-j]$ e $j \in [0, n-2]$, abbiamo
$T(m) = O(n)$
La funzione Insert() sposta dunque il valore minimo trovato dopo al minimo precedente, in modo da ricostruire alla fine un array ordinato. Il caso peggiore sulla coppia $(j,m)$ si avrà se il minimo è in fondo all'array ($m = n-1$) e l'indice $j$ ($j = 0$) è all'inizio, in questo caso bisogna far scorrere il minimo per tutte le possibili posizioni dell'array.
Il caso migliore invece si ha se $m = j$, in questo caso il minimo è già nella posizione corretta e non bisogna fare niente.
x = A[m] $\rightarrow c_{1}$
for ( k=m ; k>j ; k-- ) $\rightarrow (j-m)(c_{2} + c_{3})$
A[k] = A[k-1] $\rightarrow (j-m)(c_{4})$
A[j] = x $\rightarrow c_{1}$
$c_{1}$, $c_{2}$, $c_{3}$ e $c_{4}$ sono costanti definite in modo similare a prima. Abbiamo quindi
$T(i) = c_{1} + (j-m)(c_{2} + c_{3}) + (j-m)(c_{4}) + c_{1} = 2c_{1} + (j-m)(c_{2} + c_{3} + c_{4})$
Il caso peggiore risulta dunque
$T(i) = O(n)$
unendo tutto abbiamo
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + O(n) + O(n))$
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + 2O(n)) $ -> Somma degli $O(n)$
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + O(n)) $ -> Inserimento della costante nell'$O(n)$
$ T(S) = c_{1} + (n-2)*O(n) $ -> Somma tra costanti e $O(n)$
$ T(S) = c_{1} + O(n^2) $ -> Prodotto tra $O(n)$ e termine dello stesso ordine $n-2$.
$ T(S) = O(n^2) $ -> Somma tra costante e $O(n^2)$
e quindi il tempo finale è $O(n^2)$.
A parte gli altri algoritmi che migliorano il tempo usando tecniche e filosofie diverse, la scelta più facile da fare per migliorare il selection sort è cambiare il modo di calcolare il minimo, ovvero usando un heap (e mantenendo pressochè invariato tutto il resto). Ciò porta all'heapsort, che va in $O(nlogn)$ in tempo
.
Iniziando dalla funzione generale, non ci sono possibili scelte o altre variazioni, per cui caso migliore medio e peggiore sono uguali:
n = len(A) $\rightarrow c_{1}$
for ( j=0 ; j<=n-2 ; j++) $\rightarrow (n-2)(c_{2} + c_{3})$
min = Min( A, j ) $\rightarrow (n-2)T(m)$
Insert( A, j, min ) $\rightarrow (n-2)T(i)$
da cui
$T(S) = c_{1} + (n-2)(c_{2} + c_{3}) + (n-2)T(m) + (n-2)T(i) $
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + T(m) + T(i))$
dove $c_{1}$ è il tempo di assegnamento e calcolo della lunghezza dell'array $A$ (in teoria sarebbe $O(n)$, ma supponiamo di averlo come dato memorizzato durante la costruzione dell'array). $c_{2}$ e $c_{3}$ sono i tempi di controllo del flag ($j \leq (n-2)$ e dell'incremento unitario $j++$, che possiamo pensare costanti. Dobbiamo valutare $T(m)$ e $T(i)$, tempi delle due funzioni Min() e Insert() . Queste avranno a prescindere dei tempi migliori, medi e peggiori diversi, dato che dipendono da parametri in ingresso, ma in realtà dato che vengono richiamate sia con valori tali da ottenere i tempi migliori che con valori tali da ottenere i tempi peggiori (in quanto il for scorre per forza tutti i valori su $j$), non bisogna spezzare il calcolo del tempo nei vari casi.
Per Min() , il caso peggiore si ha con $j = 0$, in quanto deve scorrere per forza tutto l'array per trovare il minimo. il migliore si ha con $j = l(A)-1 = n-1$, dato che trova il minimo immediatamente. Mediamente (ovvero con $j$ generico tra $0$ e $n-1$) otteniamo
min = A[j] $\rightarrow c_{1}$
for ( k= j+1 ; k
min=A[k] $\rightarrow K*c_{1})$
return min $ c_{4}$
dove $c_{1}$ è il costo di un assegnamento di intero, $c_{2}$ è il costo del controllo della condizione $k
Il termine $K$ è il numero di IF positivi, ovvero quante volte viene aggiornato il valore minimo. Il caso migliore ($K=0$) si ha quando il minimo risulta il primo valore considerato $A[j]$, e quindi non ci sono aggiornamenti. Il caso peggiore ($K=n-j$) si ha invece se l'array è ordinato in ordine decrescente (e quindi il minimo è l'ultimo valore).
$T(m) = c_{1} + (n-j)(c_{2}+c_{3}) + (n-j)*c_{2} + K*c_{1} = (K+1)*c_{1} + (n-j)(2c_{2}+c_{3})$
Siccome $K \in [0, n-j]$ e $j \in [0, n-2]$, abbiamo
$T(m) = O(n)$
La funzione Insert() sposta dunque il valore minimo trovato dopo al minimo precedente, in modo da ricostruire alla fine un array ordinato. Il caso peggiore sulla coppia $(j,m)$ si avrà se il minimo è in fondo all'array ($m = n-1$) e l'indice $j$ ($j = 0$) è all'inizio, in questo caso bisogna far scorrere il minimo per tutte le possibili posizioni dell'array.
Il caso migliore invece si ha se $m = j$, in questo caso il minimo è già nella posizione corretta e non bisogna fare niente.
x = A[m] $\rightarrow c_{1}$
for ( k=m ; k>j ; k-- ) $\rightarrow (j-m)(c_{2} + c_{3})$
A[k] = A[k-1] $\rightarrow (j-m)(c_{4})$
A[j] = x $\rightarrow c_{1}$
$c_{1}$, $c_{2}$, $c_{3}$ e $c_{4}$ sono costanti definite in modo similare a prima. Abbiamo quindi
$T(i) = c_{1} + (j-m)(c_{2} + c_{3}) + (j-m)(c_{4}) + c_{1} = 2c_{1} + (j-m)(c_{2} + c_{3} + c_{4})$
Il caso peggiore risulta dunque
$T(i) = O(n)$
unendo tutto abbiamo
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + O(n) + O(n))$
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + 2O(n)) $ -> Somma degli $O(n)$
$ T(S) = c_{1} + (n-2)(c_{2} + c_{3} + O(n)) $ -> Inserimento della costante nell'$O(n)$
$ T(S) = c_{1} + (n-2)*O(n) $ -> Somma tra costanti e $O(n)$
$ T(S) = c_{1} + O(n^2) $ -> Prodotto tra $O(n)$ e termine dello stesso ordine $n-2$.
$ T(S) = O(n^2) $ -> Somma tra costante e $O(n^2)$
e quindi il tempo finale è $O(n^2)$.
A parte gli altri algoritmi che migliorano il tempo usando tecniche e filosofie diverse, la scelta più facile da fare per migliorare il selection sort è cambiare il modo di calcolare il minimo, ovvero usando un heap (e mantenendo pressochè invariato tutto il resto). Ciò porta all'heapsort, che va in $O(nlogn)$ in tempo
.
Ti ringrazio per l'analisi dettagliata della complessità, molto chiara 
L'Heap e tutte le operazioni su di esso sono davvero sorprendenti. Da pochi giorni l'ho studiato per bene e penso che molte strutture dati di vari linguaggi di programmazione utilizzino una struttura ad heap.
L'Heap e tutte le operazioni su di esso sono davvero sorprendenti. Da pochi giorni l'ho studiato per bene e penso che molte strutture dati di vari linguaggi di programmazione utilizzino una struttura ad heap.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo