Comparație sortare
| n | Jurnalul de bord 2 Int ( n ! ) {\displaystyle \left\iceil \log _{2} (n!) \ dreapta \ rceil }
|
minim |
|---|---|---|
| 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 sau 46 |
| 17 | 49 | 49 sau 50 |
| 18 | 53 | 53 sau 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | Jurnalul de bord 2 Int ( n ! ) {\displaystyle \left\iceil \log _{2} (n!) \ dreapta \ rceil }
|
n log 2 n − n ln 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 |
la numărul minim real de comparații (de la OEIS: A036604) necesar pentru a sorta o listă de n articole (în cel mai rău caz). Mai jos: folosind aproximarea lui Stirling, această limită inferioară este bine aproximată de n log 2 n-n ln ln 2 {\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}
.
Numărul de comparații pe care un algoritm de sortare comparativă le necesită crește proporțional cu n log ( n ) {\displaystyle n\log (n)}
, unde n {\displaystyle n}
este numărul de elemente pentru a sorta. Această legătură este asimptotică strânsă.
având în vedere o listă de numere distincte (putem presupune acest lucru deoarece aceasta este o analiză în cel mai rău caz), există n permutări factoriale exact una dintre ele fiind lista în ordine sortată. Algoritmul de sortare trebuie să obțină suficiente informații din comparații pentru a identifica permutarea corectă. Dacă algoritmul se finalizează întotdeauna după cel mult f(n) pași, nu poate distinge mai mult de 2F (n) cazuri, deoarece tastele sunt distincte și fiecare comparație are doar două rezultate posibile. Prin urmare,
2 f ( n) nu ! {\displaystyle 2^{f(n)}\geq n!}
, sau echivalent f ( n) log 2 ( n) – log 2 (n ! ) . {\displaystyle f (N) \geq \ log _{2}(n!).}
privind primul n / 2 {\displaystyle n/2}
factorii lui n ! = n (n − 1) 1 {\displaystyle n!=n (n-1)\cdots 1}
, obținem log 2 (n! ) ≥ log 2 ( ( n 2 ) n 2 ) = n log 2 n log 2 − n 2 = Θ ( n log n ) . {\displaystyle \ log _ {2}(n!) \ geq \log _ {2} \ stânga (\stânga ({\frac {n}{2}}\dreapta)^{\frac {n}{2}}\dreapta)={\frac {n}{2}} {\frac {\log n} {\log 2}}-{\frac {n}{2}}=\Theta (n \ log n).}
log 2 ( n ! ) = In (n log in ) . {\displaystyle \ log _ {2}(n!) = \Omega (n \ log n).}
aceasta oferă partea inferioară a creanței. O legătură mai bună poate fi dată prin aproximarea lui Stirling.
o limită superioară identică rezultă din existența algoritmilor care ating această limită în cel mai rău caz, cum ar fi heapsort și mergesort.
argumentul de mai sus oferă o limită inferioară absolută, mai degrabă decât numai asimptotică, a numărului de comparații, și anume jurnalul 2 al lui hectolitru ( n ! ) {\displaystyle \left\iceil \log _{2} (n!) \dreapta\rceil }
comparații. Această limită inferioară este destul de bună (poate fi abordată într-o toleranță liniară printr-un simplu sortare de îmbinare), dar se știe că este inexact. De exemplu, jurnalul de la 2 la 2 ( 13 ! ) = 33 {\displaystyle \left\iceil \log _{2} (13!) \dreapta\rceil =33}
, dar numărul minim de comparații pentru a sorta 13 elemente s-a dovedit a fi 34.
determinarea numărului exact de comparații necesare pentru a sorta un anumit număr de intrări este o problemă dificilă din punct de vedere al calculului chiar și pentru N mic și nu se cunoaște o formulă simplă pentru soluție. Pentru unele dintre puținele valori concrete care au fost calculate, a se vedea OEIS: a036604.
limita inferioară pentru numărul mediu de comparațiimedit
o limită similară se aplică numărului mediu de comparații. Presupunând că
- toate tastele sunt distincte, adică fiecare comparație va da fie a > b, fie a < b, și
- intrarea este o permutare aleatorie, aleasă uniform din setul tuturor permutărilor posibile ale n elemente,
este imposibil să se determine în ce ordine este intrarea cu mai puțin de log2 (n!) comparații în medie.
acest lucru poate fi văzut cel mai ușor folosind concepte din teoria informației. Entropia Shannon a unei astfel de permutări aleatorii este log2 (n!) biți. Deoarece o comparație poate da doar două rezultate, cantitatea maximă de informații pe care o oferă este de 1 bit. Prin urmare, după k comparații entropia rămasă a permutării, având în vedere rezultatele acestor comparații, este cel puțin log2(n!)- K biți în medie. Pentru a efectua sortarea, sunt necesare informații complete, astfel încât entropia rămasă trebuie să fie 0. Rezultă că k trebuie să fie cel puțin log2 (n!) în medie.
limita inferioară derivată prin teoria informației este formulată ca ‘limită inferioară informațională-teoretică’. Limita inferioară teoretică a informației este corectă, dar nu este neapărat cea mai puternică limită inferioară. Și, în unele cazuri, limita inferioară informațională teoretică a unei probleme poate fi chiar departe de adevărata limită inferioară. De exemplu, limita inferioară informațională teoretică a selecției este log 2 log 2 ( n) log {\displaystyle \left\lceil \log _{2} (n) \ right \ rceil }
întrucât N − 1 {\displaystyle n-1}
comparațiile sunt necesare de un argument contradictoriu. Interacțiunea dintre limita inferioară teoretică a informațiilor și limita inferioară adevărată seamănă mult cu o funcție cu valoare reală care limitează mai jos o funcție întreagă. Cu toate acestea, acest lucru nu este exact corect atunci când se ia în considerare cazul mediu.
pentru a descoperi ce se întâmplă în timp ce analizăm cazul mediu, cheia este că la ce se referă media? Medierea peste ce? Cu unele cunoștințe de teoria informației, limita inferioară teoretică a informațiilor este medie peste setul tuturor permutărilor în ansamblu. Dar orice algoritmi de calculator (sub ceea ce se crede în prezent) trebuie să trateze fiecare permutare ca o instanță individuală a problemei. Prin urmare, limita medie inferioară pe care o căutăm este medie pentru toate cazurile individuale.
pentru a căuta limita inferioară referitoare la nerealizabilitatea computerelor, adoptăm Modelul arborelui decizional. Să reformulăm puțin din obiectivul nostru. În modelul arborelui de decizie, limita inferioară care trebuie afișată este limita inferioară a lungimii medii a căilor rădăcină-frunză ale unui n ! {\displaystyle n!}
– arbore binar cu frunze (în care fiecare frunză corespunde unei permutări). Ar fi convins să spunem că un arbore binar complet echilibrat atinge minimul lungimii medii. Cu unele calcule atente, pentru un arbore binar complet echilibrat cu n ! {\displaystyle n!}
frunze, lungimea medie a căilor rădăcină-frunză este dată de (2 n ! – 2 bușteni de la 2 la 2 la n ! + 1) bușteni 2-log 2-log 2-log 2-log ! + (2-2 – 2-n ! + 1 − n ! ) bușteni de la 2 la 2 la ! o sută n ! {\displaystyle {\frac {(2n!-2 ^ {\lfloor \ log _ {2}n!\rfloor + 1}) \cdot \iceil \ log _{2}n!\ rceil +(2 ^ {\lfloor \ log _ {2}n!\ rfloor + 1} – n!) \ cdot \ lfloor \log _ {2}n!\ rfloor} {n!}}}
de exemplu, pentru n = 3, limita inferioară teoretică a informațiilor pentru cazul mediu este de aproximativ 2,58, în timp ce limita inferioară medie derivată prin modelul arborelui de decizie este de 8/3, aproximativ 2,67.
în cazul în care mai multe elemente pot avea aceeași cheie, nu există o interpretare statistică evidentă pentru termenul “caz mediu”, deci un argument precum cel de mai sus nu poate fi aplicat fără a face presupuneri specifice despre distribuția cheilor.
