Complessitą degli ordinamenti ingenui
Bubble Sort
L'istruzione SCAMBIA() viene eseguita ogni volta che SE() ALLORA ha successo; consideriamo il caso pessimo, cioè che succeda a ogni passo. Quante volte viene eseguita?| i | j | T |
|---|---|---|
| 1 | 1...n-1 | n-1 |
| 2 | 1...n-2 | n-2 |
| ... | ... | ... |
| n-1 | 1...(n-(n-2)) 1...2 | 2 |
| n-1 | 1...(n-(n-1)) 1...1 | 1 |
Quindi
T(n) = (n-1)+(n-2)+...+1.
Quanto vale la somma?
Sappiamo che 1+2+...N = ½N(N+1) e quindi
T(n) = ½(n-1)n = ½n2-½n.
La complessità in tempo asintotica dell'algoritmo di ordinamento Bubble Sort è O(n2), sia per il numero di confronti che per il numero di scambi.
Nel caso ottimo, il vettore già ordinato, il numero di scambi è zero ma rimane quadratico il numero di confronti.
Selection Sort
Quante volte viene eseguita l'istruzione SE(...) ALLORA?| i | j | T |
|---|---|---|
| 0 | 1 ... n-1 | n-1 |
| 1 | 2 ... n-1 | n-2 |
|
... |
... |
... |
| n-2 | n-1 ... n-1 |
1 |
Calcolo di T(n)
T(n) = (n-1)+(n-2)+...+1
Quanto vale la somma? Sappiamo che
1+2+...N = ½N(N+1)
e quindi
T(n) = ½(n-1)n = ½n2-½n.
La complessitą in tempo asintotica dell'algoritmo di ordinamento selection sort č O(n2), per il numero di confronti.
Il numero di scambi č n-1, lineare.
