Complessità: ordinamenti

Per il problema dell’ordinamento esistono molti algoritmi con complessità diverse

Ingenui	selection sort, bubble sort, shaker sort, insertion sort	O(n2)
Intermedi	shell sort	O(n~1.2)
Evoluti	merge sort, quick sort, heap sort	O(n logn)

Si può dimostrare che non può esistere un algoritmo di ordinamento con complessità in tempo minore di O(n log n).
Il problema dell’ordinamento ha complessità O(n log n).

---

Confrontiamo la complessità in tempo degli algoritmi di ordinamento ingenui con quella degli algoritmi evoluti, al variare della dimensione del problema

n		T(n) = n2 (ingenuo)		T(n) = n log2n (evoluto)
210	~103	220	~106	210 · 10	~104
220	~106	240	~1012	220 · 20	~2 · 107
230	~109	260	~1018	230 · 30	~3 · 1010
240	~1012	280	~1024	240 · 40	~4 · 1013

Se il computer esegue 10⁶ operazioni elementari al secondo allora i tempi di attesa sono

n	n2		Tempo di attesa	n log2n		Tempo di attesa
103	106	100	1 secondo	~104	~10-2	~0.01 secondi
104	108	102	1 minuto e 40 secondi	~1,3 · 105	~1,3 · 10-1	~0,13 secondi
105	1010	104	2 ore, 46 minuti e 40 secondi	~1,7 · 106	~1,7 · 101	~1,7 secondi
106	1012	106	11 giorni, 13 ore, 46 minuti e 40 secondi	~2 · 107	~2 · 101	~20 secondi
109	1018	1012	~32 mila anni	~3 · 1010	~3 · 104	> 8 ore
1010	1020	1014	~3 milioni di anni	~3,3 · 1011	~3,3 · 105	< 4 giorni

Se il computer esegue 10⁹ operazioni elementari al secondo allora i tempi di attesa sono

n	n2		Tempo di attesa	n log2n		Tempo di attesa
103	106	10-3	~0,001 secondi	~104	~10-5	~0.00001 secondi
104	108	10-1	~0,1 secondi	~1,3 · 105	~1,3 ·10-4	~0.00013 secondi
105	1010	101	10 secondi	~1,7 · 106	~1,7 · 10-3	~0.0017 secondi
106	1012	103	~17 minuti	~2 · 107	~2 · 10-2	~0.02 secondi
109	1018	109	~30 anni	~3 · 1010	~3 · 101	~30 secondi
1010	1020	1011	~3000 anni	~3,3 · 1011	~3,32 · 102	> 5 minuti

Utilizzare un algoritmo ingenuo con milioni di dati porta a tempi di attesa inaccettabili!!!