Qualunque testo decente sugli algoritmi spiegherà quanto siano veloci algoritmi di ordinamento come quicksort e heapsort, ma non ci vuole una matematica folle per dimostrare che sono asintoticamente veloci come è possibile ottenere.
Una nota pedante sulla notazione
La maggior parte degli informatici usa la notazione big-O per significare “asintoticamente uguale, fino a un fattore di scala costante”, che non è esattamente ciò che significa per gli altri matematici. Scusa, userò big-O come nei libri di testo di CS, ma almeno non lo mischierò con altre notazioni matematiche.
Ordinamento basato sul confronto
Guardiamo il caso speciale degli algoritmi che confrontano i valori due alla volta (come quicksort e heapsort, e molti altri algoritmi popolari). Le idee possono essere estese a tutti gli algoritmi di ordinamento in seguito.
Un semplice argomento di conteggio per il caso peggiore
Supponiamo di avere un array di quattro elementi, tutti diversi, in ordine casuale. Potete ordinarlo confrontando solo una coppia di elementi? Ovviamente no, ma ecco una buona ragione che dimostra che non si può: per definizione, per ordinare l’array, è necessario come riorganizzare gli elementi per metterli in ordine. In altre parole, dovete sapere quale permutazione è necessaria. Quante permutazioni possibili ci sono? Il primo elemento potrebbe essere spostato in uno dei quattro posti, il secondo potrebbe andare in uno dei tre rimanenti, il terzo elemento ha due opzioni, e l’ultimo elemento deve prendere il posto rimanente. Quindi ci sono 4×3×2×1=4!=244 × 3 × 2 × 1 = 4! = 24 possibili permutazioni tra cui scegliere, ma ci sono solo due risultati possibili dal confronto di due cose diverse: “PIÙ GRANDE” e “PIÙ PICCOLO”. Se tu facessi una lista di tutte le possibili permutazioni, potresti decidere che “PIÙ GRANDE” significa che hai bisogno della permutazione #8 e “PIÙ PICCOLA” significa che hai bisogno della permutazione #24, ma non c’è modo di sapere quando hai bisogno delle altre 22 permutazioni.
Con due confronti, hai 2×2=42 volte 2 = 4 possibili risultati, che ancora non è abbastanza. Non potete ordinare ogni possibile matrice mescolata se non fate almeno cinque confronti (25=322^5 = 32). Se W(N)W(N) è il numero peggiore di confronti necessari per ordinare NN elementi diversi usando qualche algoritmo, possiamo dire
2W(N)≥N!2^{W(N)} \geq N!
Prendendo un logaritmo base 2,
W(N)≥log2N!W(N) \geq \log_2{N!}
Asintoticamente, N!N! cresce come NNN^N (vedi anche la formula di Stirling), quindi
W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}
E questo è un limite O(NlogN)O(N\log N) sul caso peggiore solo per contare le uscite.
Caso medio dalla teoria dell’informazione
Possiamo ottenere un risultato più forte se estendiamo l’argomento del conteggio con un po’ di teoria dell’informazione. Ecco come potremmo usare un algoritmo di ordinamento come un codice per trasmettere informazioni:
- Penso a un numero – diciamo, 15
- Cerco la permutazione #15 dalla lista delle permutazioni di quattro elementi
- Eseguo l’algoritmo di ordinamento su questa permutazione e registro tutti i risultati del confronto “PIÙ GRANDE” e “PIÙ PICCOLO”
- Trasmetto i risultati del confronto a te in codice binario
- Tu reinserisci il mio algoritmo di ordinamento, passo dopo passo, facendo riferimento alla mia lista di risultati di confronto quando necessario
- Ora che sai come ho riorganizzato il mio array per renderlo ordinato, puoi invertire la permutazione per capire il mio array originale
- Tu cerchi il mio array originale nella lista di permutazione per capire che ho trasmesso il numero 15
Ok, è un po’ strano, ma si può fare. Questo significa che gli algoritmi di ordinamento sono vincolati dalle stesse leggi degli schemi di codifica normali, compreso il teorema che dimostra che non esiste un compressore di dati universale. Ho trasmesso un bit per ogni confronto che l’algoritmo fa, quindi, in media, il numero di confronti deve essere almeno il numero di bit necessari per rappresentare i miei dati, secondo la teoria dell’informazione. Più tecnicamente, il numero medio di confronti deve essere almeno l’entropia di Shannon dei miei dati di input, misurata in bit. L’entropia è una misura matematica del contenuto informativo, o imprevedibilità, di qualcosa.
Se ho una matrice di NN elementi che potrebbero essere in qualsiasi ordine possibile senza bias, allora l’entropia è massimizzata ed èlog2N!\log_2{N!} bit. Questo dimostra che O(NlogN)O(N\log{N}) è una media ottimale per un ordinamento basato sul confronto con input arbitrario.
Questa è la teoria, ma come si confrontano gli algoritmi di ordinamento reali? Qui sotto c’è un grafico del numero medio di confronti necessari per ordinare un array. Ho confrontato l’optimum teorico con il quicksort ingenuo e il Ford-Johnson merge-insertion sort, che è stato progettato per minimizzare i confronti (anche se raramente è più veloce del quicksort nel complesso, perché c’è di più nella vita che minimizzare i confronti). Da quando è stato sviluppato nel 1959, il merge-insertion sort è stato modificato per spremere qualche confronto in più, ma il grafico mostra che è già quasi ottimale.
È bello quando un po’ di teoria dà un risultato pratico così stretto.
Sommario finora
Ecco cosa è stato dimostrato finora:
- Se l’array può iniziare in qualsiasi ordine, sono necessari almeno O(NlogN)O(N\log{N}) confronti nel caso peggiore
- Il numero medio di confronti deve essere almeno l’entropia dell’array, che è O(NlogN)O(N\log{N}) per input casuale
Nota che #2 permette agli algoritmi di ordinamento basati sul confronto di essere più veloci di O(NlogN)O(N\log{N}) se l’input è a bassa entropia (in altre parole, più prevedibile). Il merge sort è vicino a O(N)O(N) se l’input contiene molti subarray ordinati. Insertion sort è vicino a O(N)O(N) se l’input è un array che è stato ordinato prima di essere perturbato un po’. Nessuno di loro batte O(NlogN)O(N\log{N}) nel caso peggiore, a meno che alcuni ordinamenti di array siano impossibili come input.
Algoritmi di ordinamento generali
Gli ordinamenti basati sul confronto sono un caso speciale interessante nella pratica, ma non c’è nulla di teoricamente speciale suCMP rispetto a qualsiasi altra istruzione su un computer. Entrambi gli argomenti di cui sopra possono essere generalizzati a qualsiasi algoritmo di ordinamento se si notano un paio di cose:
- La maggior parte delle istruzioni del computer hanno più di due possibili uscite, ma ne hanno comunque un numero limitato
- Il numero limitato di uscite significa che un’istruzione può elaborare solo una quantità limitata di entropia
Questo ci dà lo stesso limite inferiore O(NlogN)O(N\log{N}) sul numero di istruzioni. Qualsiasi computer fisicamente realizzabile può elaborare solo un numero limitato di istruzioni alla volta, quindi anche questo è un limite inferiore O(NlogN)O(N\log{N}) sul tempo richiesto.
Ma che dire degli algoritmi “più veloci”?
L’implicazione pratica più utile del limite generale O(NlogN)O(N\log{N}) è che se si sente parlare di qualsiasi algoritmo asintoticamente più veloce, si sa che deve “barare” in qualche modo. Ci dev’essere qualche fregatura che significa che non è un algoritmo di ordinamento di uso generale che si adatta a matrici arbitrariamente grandi. Potrebbe ancora essere un algoritmo utile, ma è una buona idea leggere attentamente la stampa fine.
Un esempio ben noto è il radix sort. Viene spesso chiamato un algoritmo di ordinamento O(N)O(N), ma la fregatura è che funziona solo se tutti i numeri stanno in kk bit, ed è davvero O(kN)O(kN).
Cosa significa questo in pratica? Supponiamo di avere una macchina a 8 bit. Potete rappresentare 28=2562^8 = 256 numeri diversi in 8 bit, quindi se avete un array di migliaia di numeri, avrete delle duplicazioni. Questo potrebbe andare bene per alcune applicazioni, ma per altre è necessario passare ad almeno 16 bit, che possono rappresentare in modo distinto 216=65.5362^16 = 65.536 numeri. 32 bit supporteranno 232=4.294.967.2962^32 = 4.294.967.296 numeri diversi. Man mano che la dimensione dell’array sale, anche il numero di bit necessari tenderà a salire. Per rappresentare distintamente NN numeri diversi, avrete bisogno di k≥log2Nk \geq \log_2{N}. Quindi, a meno che non vi vada bene avere molti duplicati nel vostro array, O(kN)O(kN) è effettivamente O(NlogN)O(N\log{N}).
La necessità di O(NlogN)O(N\log{N}) di dati di input nel caso generale prova effettivamente il risultato complessivo da solo. Questo argomento non è così interessante nella pratica perché raramente abbiamo bisogno di ordinare miliardi di interi su una macchina a 32 bit, e se qualcuno ha raggiunto i limiti di una macchina a 64 bit, non l’ha detto al resto di noi.