Ordinamento di confronto
| n | log registro 2! (n! ) {{\displaystyle \ left\lceil \ log _{2} (n!) \ right \ rceil}
 |
Minimo |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 3 | 3 |
| 4 | 5 | 5 |
| 5 | 7 | 7 |
| 6 | 10 | 10 |
| 7 | 13 | 13 |
| 8 | 16 | 16 |
| 9 | 19 | 19 |
| 10 | 22 | 22 |
| 11 | 26 | 26 |
| 12 | 29 | 30 |
| 13 | 33 | 34 |
| 14 | 37 | 38 |
| 15 | 41 | 42 |
| 16 | 45 | 45 o 46 |
| 17 | 49 | 49 o 50 |
| 18 | 53 | 53 o 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | ⌈ log 2 ( n ! ) {{\displaystyle \ left\lceil \ log _{2} (n!) \ right \ rceil}
|
n log 2 n − n ln 2 {\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}
 |
| 10 | 22 | 19 |
| 100 | 525 | 521 |
| 1 000 | 8 530 | 8 524 |
| 10 000 | 118 459 | 118 451 |
| 100 000 | 1 516 705 | 1 516 695 |
| 1 000 000 | 18 488 885 | 18 488 874 |
al numero minimo effettivo di confronti (da OEIS: A036604) necessario per ordinare un elenco di n elementi (per il caso peggiore). Sotto: Usando l’approssimazione di Stirling, questo limite inferiore è ben approssimato da n log 2 n n − n ln 2 2 {\displaystyle n\log _{2}n-{\frac {n} {\ln 2}}}
.
Il numero di confronti che un confronto algoritmo di ordinamento richiede aumenta in proporzione al n log ( n ) {\displaystyle n\log(n)}
, dove n {\displaystyle n}
è il numero di elementi da ordinare. Questo limite è asintoticamente stretto.
Dato un elenco di numeri distinti (possiamo assumerlo perché questa è un’analisi del caso peggiore), ci sono n permutazioni fattoriali esattamente una delle quali è la lista in ordine ordinato. L’algoritmo di ordinamento deve ottenere informazioni sufficienti dai confronti per identificare la permutazione corretta. Se l’algoritmo viene sempre completato dopo al massimo f(n) passaggi, non può distinguere più di 2f(n) casi perché le chiavi sono distinte e ogni confronto ha solo due possibili risultati. Pertanto,
2 f ( n ) ≥ n ! {\stile di visualizzazione 2^{f(n)}\geq n!}
, o equivalentemente f ( n ) ≥ log 2! (n! ) . {\stile di visualizzazione f(n) \geq \ log _{2}(n!).}
Guardando il primo n / 2 {\displaystyle n/2}
fattori di n ! = n (n − 1 ) ⋯ 1 {\displaystyle n!=n (n-1)\cdots 1}
, otteniamo log 2! (n! ) ≥ log 2 n ( ( n 2 ) n 2 ) = n 2 log n n log log 2 − n 2 = Θ ( n log n n ) . {\displaystyle \ log _{2} (n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).}
registro 2! (n! ) = Ω (n log n n). {\displaystyle \ log _{2} (n!) = \ Omega (n \ log n).}
Ciò fornisce la parte inferiore del reclamo. Un legame migliore può essere dato tramite l’approssimazione di Stirling.
Un limite superiore identico deriva dall’esistenza degli algoritmi che raggiungono questo limite nel peggiore dei casi, come heapsort e mergesort.
L’argomento precedente fornisce un limite inferiore assoluto, piuttosto che solo asintotico, sul numero di confronti, vale a dire log log 2! (n! ) {{\displaystyle \ left\lceil \ log _{2} (n!) \ destra \ rceil }
confronti. Questo limite inferiore è abbastanza buono (può essere avvicinato all’interno di una tolleranza lineare da un semplice tipo di unione), ma è noto per essere inesatto. Ad esempio, log log 2 ((13 ! ) ⌉ = 33 {\displaystyle \ left\lceil \ log _{2} (13!) \ destra \ rceil =33}
, ma il numero minimo di confronti per ordinare 13 elementi è stato dimostrato essere 34.
Determinare il numero esatto di confronti necessari per ordinare un dato numero di voci è un problema computazionalmente difficile anche per small n, e non è nota alcuna formula semplice per la soluzione. Per alcuni dei pochi valori concreti che sono stati calcolati, vedere OEIS: A036604.
Limite inferiore per il numero medio di comparisonsEdit
Un limite simile si applica al numero medio di confronti. Supponendo che
- tutte le chiavi siano distinte, cioè ogni confronto darà a > b o a < b, e
- l’input è una permutazione casuale, scelta uniformemente dall’insieme di tutte le possibili permutazioni di n elementi,
è impossibile determinare in quale ordine si trova l’input con meno di log2(n!) confronti in media.
Questo può essere visto più facilmente usando concetti dalla teoria dell’informazione. L’entropia di Shannon di una tale permutazione casuale è log2 (n!) bit. Poiché un confronto può dare solo due risultati, la quantità massima di informazioni che fornisce è 1 bit. Pertanto, dopo i confronti k l’entropia rimanente della permutazione, dati i risultati di tali confronti, è almeno log2(n!)- k bit in media. Per eseguire l’ordinamento, sono necessarie informazioni complete, quindi l’entropia rimanente deve essere 0. Ne consegue che k deve essere almeno log2 (n!) in media.
Il limite inferiore derivato dalla teoria dell’informazione è formulato come “limite inferiore teorico dell’informazione”. Il limite inferiore teorico-informativo è corretto ma non è necessariamente il limite inferiore più forte. E in alcuni casi, il limite inferiore teorico-informativo di un problema può anche essere lontano dal vero limite inferiore. Per esempio, le informazioni teorico-limite inferiore di selezione è ⌈ log 2 ( n ) ⌉ {\displaystyle \left\lceil \log _{2}(n)\right\rceil }
considerando che n − 1 {\displaystyle n-1}
confronti sono necessari da un contraddittorio argomento. L’interazione tra il limite inferiore teorico dell’informazione e il limite inferiore vero sono molto simili a una funzione a valore reale che delimita una funzione intera. Tuttavia, questo non è esattamente corretto quando viene considerato il caso medio.
Per scoprire cosa succede analizzando il caso medio, la chiave è che a cosa si riferisce la “media”? Una media su cosa? Con una certa conoscenza della teoria dell’informazione, le medie del limite inferiore dell’informazione-teorico sull’insieme di tutte le permutazioni nel suo complesso. Ma qualsiasi algoritmo informatico (sotto quello che si crede attualmente) deve trattare ogni permutazione come un’istanza individuale del problema. Quindi, il limite medio inferiore che stiamo cercando è mediato su tutti i singoli casi.
Per cercare il limite inferiore relativo alla non realizzabilità dei computer, adottiamo il modello ad albero decisionale. Riformuliamo un po ‘ il nostro obiettivo. Nel modello ad albero decisionale, il limite inferiore da mostrare è il limite inferiore della lunghezza media dei percorsi radice-foglia di un n ! {\stile di visualizzazione n!}
– albero binario foglia (in cui ogni foglia corrisponde a una permutazione). Sarebbe convinto di dire che un albero binario completo bilanciato raggiunge il minimo della lunghezza media. Con alcuni calcoli accurati, per un albero binario completo bilanciato con n ! {\stile di visualizzazione n!}
foglie, la lunghezza media dei percorsi radice-foglia è data da (2 n ! – 2 log registro 2 n n ! log + 1) log registro 2 n n ! log + (2 log registro 2 n n ! ⌋ + 1-n ! ) log registro 2 n n ! n n ! {\stile di visualizzazione {\frac {(2n!-2^{\lfloor \ log _ {2} n!\ rfloor + 1}) \ cdot \ lceil \ log _ {2} n!\rceil + (2^{\lfloor \ log _ {2} n!\ rpiano + 1} – n!) \ cdot \ lfloor \ log _ {2} n!\ rfloor} {n!}}}
Ad esempio, per n = 3, il limite inferiore teorico dell’informazione per il caso medio è di circa 2,58, mentre il limite inferiore medio derivato tramite il modello ad albero decisionale è 8/3, circa 2,67.
Nel caso in cui più elementi possano avere la stessa chiave, non esiste un’interpretazione statistica ovvia per il termine “caso medio”, quindi un argomento come il precedente non può essere applicato senza formulare ipotesi specifiche sulla distribuzione delle chiavi.
