Sortuj porównanie
| n | ⌈ log 2 (n ! )⌉ {\displaystyle \left\lceil \log _{2} (n!) \ right \ rceil }
 |
minimalna |
|---|---|---|
| 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 lub 46 |
| 17 | 49 | 49 lub 50 |
| 18 | 53 | 53 lub 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 magazyn 2 n − n ln 2 {\styl wyświetlania n\log _{2}, n-{\frakcja {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 |
do rzeczywistej minimalnej liczby porównań (z OEIS: A036604) wymaganej do sortowania listy N pozycji (w najgorszym przypadku). Poniżej: używając aproksymacji Stirlinga, ta dolna granica jest dobrze przybliżona przez n log 2 n-N ln 2 {\displaystyle n \ log _{2}n – {\frac {n}{\ln 2}}}
.
liczba porównań, których wymaga algorytm sortowania porównań, wzrasta proporcjonalnie do n log (n) {\displaystyle n\log (n)}
, gdzie n {\displaystyle n}
jest liczbą elementów do sortowania. Wiązanie to jest asymptotycznie ciasne.
biorąc pod uwagę listę różnych liczb (możemy to założyć, ponieważ jest to analiza najgorszego przypadku), istnieje n permutacji silnia, z których dokładnie jedna jest listą w porządku posortowanym. Algorytm sortowania musi uzyskać wystarczającą ilość informacji z porównań, aby zidentyfikować prawidłową permutację. Jeśli algorytm zawsze kończy się co najwyżej po krokach f(n), nie może rozróżnić więcej niż 2F(n) przypadków, ponieważ klucze są różne i każde porównanie ma tylko dwa możliwe wyniki. Dlatego
2 f ( n ) ≥ n ! {\displaystyle 2^{f (n)} \ geq n!}
, lub równoważnie f (n ) ≥ log 2 (n ! ) . {\displaystyle f (n) \ geq \ log _ {2} (n!).}
patrząc na pierwsze n / 2 {\displaystyle n/2}
= n (n − 1 ) ⋯ 1 {\displaystyle n!=N (n-1)\cdots 1}
, otrzymujemy log 2 (n ! ) ≥ log 2 ( ( N 2) n 2) = n 2 log n log 2 − N 2 = Θ ( n log 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).}
log 2 (n ! ) = Ω (n log n). {\displaystyle \ log _{2} (n!) =\Omega (n\log N).}
stanowi to dolną część roszczenia. Lepsze wiązanie można uzyskać poprzez przybliżenie Stirlinga.
identyczna górna granica wynika z istnienia algorytmów, które osiągają tę granicę w najgorszym przypadku, jak heapsort i mergesort.
powyższy argument podaje bezwzględną, a nie tylko asymptotyczną dolną granicę liczby porównań, mianowicie ⌈ log 2 (n ! )⌉ {\displaystyle \left\lceil \log _{2} (n!) \ right\rceil }
Ta dolna granica jest dość dobra (można do niej podejść w tolerancji liniowej przez prosty rodzaj scalania), ale wiadomo, że jest niedokładna. Na przykład ⌈ log 2 (13 ! )⌉ = 33 {\displaystyle \left\lceil \log _{2} (13!) \ right\rceil =33}
, okazało się jednak, że minimalna liczba porównań do sortowania 13 elementów wynosi 34.
ustalenie dokładnej liczby porównań potrzebnych do sortowania danej liczby wpisów jest obliczeniowo trudnym problemem nawet dla małego n i nie jest znany prosty wzór na rozwiązanie. Niektóre z kilku konkretnych wartości, które zostały obliczone, zobacz OEIS: A036604.
dolna granica dla średniej liczby porównańedytuj
podobna granica dotyczy średniej liczby porównań. Zakładając, że
- wszystkie klucze są różne, tzn. każde porównanie da albo> b, albo < b, A
- wejście jest losową permutacją, wybraną jednolicie ze zbioru wszystkich możliwych permutacji N elementów,
nie jest możliwe określenie, w jakiej kolejności znajduje się dane wejściowe z liczbą mniejszą niż log2 (N!) porównania średnio.
można to najłatwiej dostrzec używając pojęć z teorii informacji. Entropia Shannona takiej losowej permutacji to log2 (n!) bitów. Ponieważ porównanie może dać tylko dwa wyniki, maksymalna ilość informacji, którą dostarcza, wynosi 1 bit. Dlatego po porównaniach k pozostała Entropia permutacji, biorąc pod uwagę wyniki tych porównań, wynosi co najmniej log2(n!)- K bitów średnio. Aby wykonać sortowanie, potrzebne są pełne informacje, więc pozostała Entropia musi wynosić 0. Wynika z tego, że k musi być co najmniej log2(n!) średnio.
dolna granica wywodząca się z teorii informacji jest określana jako “information-theoretic lower bound”. Informacja-teoretyczna dolna granica jest poprawna, ale niekoniecznie jest najsilniejszą dolną granicą. I w niektórych przypadkach, informacja-teoretyczne dolnej granicy problemu może być nawet daleko od prawdziwej dolnej granicy. Na przykład, informacyjnie-teoretyczna dolna granica wyboru to ⌈ log 2 (n)⌉ {\displaystyle \ left\lceil\log _{2}(n)\right \ rceil }
podczas gdy N − 1 {\displaystyle n-1}
wymagane jest porównanie argumentu przeciwstawnego. Współzależność pomiędzy informacyjnie-teoretyczną dolną granicą a prawdziwą dolną granicą jest podobna do funkcji o wartości rzeczywistej, ograniczającej funkcję całkowitą. Jednak nie jest to dokładnie poprawne, gdy rozważa się średni przypadek.
aby dowiedzieć się, co się dzieje podczas analizy przeciętnego przypadku, kluczem jest to, do czego odnosi się “średnia”? Uśrednianie czego? Z pewną znajomością teorii informacji, informacji-teoretyczne niższe wartości graniczne na zbiorze wszystkich permutacji jako całości. Ale wszelkie algorytmy komputerowe (zgodnie z tym, co uważa się obecnie) muszą traktować każdą permutację jako indywidualną instancję problemu. Stąd średnia dolna granica, której szukamy, jest uśredniona we wszystkich indywidualnych przypadkach.
aby wyszukać dolną granicę odnoszącą się do nieosiągalności komputerów, przyjmujemy Model drzewa decyzyjnego. Ujmę to inaczej, jaki jest nasz cel. W modelu drzewa decyzyjnego dolna granica, która ma być pokazana, jest dolną granicą średniej długości ścieżek korzeniowych do liści N ! {\displaystyle n!}
– drzewo binarne liści (w którym każdy liść odpowiada permutacji). Można by powiedzieć, że zbalansowane pełne drzewo binarne osiąga minimum średniej długości. Z pewnymi ostrożnymi obliczeniami, dla zbalansowanego pełnego drzewa binarnego z n ! {\displaystyle n!
liści, średnią długość ścieżek nasadowo-liściowych podaje ( 2 n ! – 2 ♣ log 2 ♣ n ! ⌋ + 1) log log 2 n ! ⌉ + ( 2 ⌊ log 2 n ! ⌋ + 1-n ! ) ⋅ ⌊ log 2 n ! ⌋ n ! {\displaystyle {\frac {(2n!-2^{\lfloor \ log _ {2} n!\ rfloor + 1}) \ cdot \lceil \ log _ {2} n!\rceil +(2^{\LF \ log _ {2} n!\ rfloor +1} – n!) \ cdot \lfloor \ log _ {2} n!\ rfloor }{n!}}}
na przykład, dla N = 3, dolna granica teoretyczna informacji dla przeciętnego przypadku wynosi około 2,58, podczas gdy średnia dolna granica uzyskana za pomocą modelu drzewa decyzyjnego wynosi 8/3, około 2,67.
w przypadku, gdy wiele elementów może mieć ten sam klucz, nie ma oczywistej interpretacji statystycznej dla terminu “średni przypadek”, więc argument taki jak powyższy nie może być zastosowany bez dokonania konkretnych założeń dotyczących rozkładu kluczy.
