The Art of Machinery

Każdy przyzwoity podręcznik algorytmiki wyjaśni jak szybkie są algorytmy sortowania takie jak quicksort i heapsort, ale nie potrzeba szalonej matematyki, aby udowodnić, że są one asymptotycznie szybkie jak to tylko możliwe.

Pedantyczna uwaga o notacji

Większość informatyków używa notacji big-O, aby oznaczać „asymptotycznie równe, aż do stałego współczynnika skalowania”, co nie jest całkiem tym, co oznacza dla innych matematyków. Przepraszam, będę używał big-O jak w podręcznikach informatyki, ale przynajmniej nie będę mieszał jej z inną notacją matematyczną.

Sortowanie oparte na porównywaniu

Przyjrzyjrzyjmy się specjalnemu przypadkowi algorytmów, które porównują wartości po dwie na raz (jak quicksort i heapsort, i większość innych popularnych algorytmów). Idee mogą być rozszerzone na wszystkie algorytmy sortowania później.

Prosty argument liczenia dla najgorszego przypadku

Załóżmy, że masz tablicę z czterema elementami, wszystkie różne, w przypadkowej kolejności. Czy możesz ją posortować, porównując tylko jedną parę elementów? Oczywiście, że nie, ale oto jeden dobry powód, który dowodzi, że nie możesz: Z definicji, aby posortować tablicę, musisz dowiedzieć się, jak zmienić układ elementów, aby umieścić je w kolejności. Innymi słowy, musisz wiedzieć, która permutacja jest potrzebna. Ile jest możliwych permutacji? Pierwszy element może zostać przeniesiony na jedno z czterech miejsc, drugi może trafić na jedno z pozostałych trzech, trzeci element ma dwie możliwości, a ostatni musi zająć pozostałe miejsce. Jest więc 4×3×2×1=4!=244 razy 3 razy 2 razy 1 = 4! = 24 możliwe permutacje do wyboru, ale są tylko dwa możliwe wyniki porównania dwóch różnych rzeczy: „DUŻE” i „MAŁE”. Jeśli zrobiłbyś listę wszystkich możliwych permutacji, mógłbyś zdecydować, że „DUŻA” oznacza, że potrzebujesz permutacji #8, a „MAŁA” oznacza, że potrzebujesz permutacji #24, ale nie ma sposobu, abyś wiedział, kiedy potrzebujesz pozostałych 22 permutacji.

Z dwoma porównaniami, masz 2×2=42 razy 2 = 4 możliwe wyjścia, co wciąż nie jest wystarczające. Nie możesz posortować każdej możliwej potasowanej tablicy, chyba że wykonasz co najmniej pięć porównań (25=322^5 = 32). Jeśli W(N)W(N) jest najgorszym przypadkiem liczby porównań potrzebnych do sortowania NN różnych elementów przy użyciu pewnego algorytmu, możemy powiedzieć

2W(N)≥N!2^{W(N)} \N!

Obliczając logarytm o podstawie 2,

W(N)≥log2N!W(N)

Asymptotycznie, N!N! rośnie jak NNN^N (zobacz też formułę Stirlinga), więc

W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = Nlog{N}

I to jest ograniczenie O(NlogN)O(Nlog N) na najgorszy przypadek tylko z liczenia wyjść.

Średni przypadek z teorii informacji

Możemy uzyskać silniejszy wynik, jeśli rozszerzymy ten argument z liczenia o odrobinę teorii informacji. Oto jak moglibyśmy użyć algorytmu sortowania jako kodu do przesyłania informacji:

1. Myślę o pewnej liczbie – powiedzmy, 15
2. Wyszukuję permutację #15 z listy permutacji czterech elementów
3. Uruchamiam algorytm sortowania na tej permutacji i zapisuję wszystkie wyniki porównania „WIĘKSZE” i „MNIEJSZE”
4. Przekazuję Ci wyniki porównania w kodzie binarnym
5. Ponownie odtwarzasz przebieg mojego algorytmu sortowania, krok po kroku, odnosząc się do mojej listy wyników porównania w razie potrzeby
6. Teraz, gdy wiesz, jak zmieniłem układ mojej tablicy, aby uczynić ją posortowaną, możesz odwrócić permutację, aby dowiedzieć się, jaka jest moja oryginalna tablica
7. Sprawdzisz moją oryginalną tablicę na liście permutacji, aby dowiedzieć się, że przesłałem liczbę 15

Dobra, to trochę dziwne, ale można to zrobić. Oznacza to, że algorytmy sortowania są związane tymi samymi prawami, co normalne schematy kodowania, w tym twierdzenie dowodzące, że nie ma uniwersalnego kompresora danych. Przekazałem jeden bit na każde porównanie, które wykonuje algorytm, więc zgodnie z teorią informacji, średnia liczba porównań musi być co najmniej równa liczbie bitów potrzebnych do reprezentacji moich danych. Mówiąc bardziej technicznie, średnia liczba porównań musi być co najmniej równa entropii Shannona moich danych wejściowych, mierzonej w bitach. Entropia jest matematyczną miarą zawartości informacji, lub nieprzewidywalności, czegoś.

Jeśli mam tablicę elementów NN, które mogą być w każdej możliwej kolejności bez uprzedzeń, wtedy entropia jest zmaksymalizowana i wynosilog2N!log_2{N!} bitów. To dowodzi, że O(NlogN)O(Nlog{N}) jest optymalną średnią dla sortowania opartego na porównywaniu z arbitralnymi danymi wejściowymi.

Taka jest teoria, ale jak wypadają prawdziwe algorytmy sortowania? Poniżej znajduje się wykres średniej liczby porównań potrzebnych do posortowania tablicy. Porównałem teoretyczne optimum z naiwnym quicksortem i sortowaniem Ford-Johnson merge-insertion, które zostało zaprojektowane w celu zminimalizowania porównań (chociaż rzadko jest szybsze niż quicksort, ponieważ w życiu chodzi o coś więcej niż minimalizowanie porównań). Od czasu jego opracowania w 1959 roku, sortowanie przez wstawianie zostało poprawione, aby wycisnąć kilka porównań więcej, ale wykres pokazuje, że jest już prawie optymalne.

To miłe, gdy trochę teorii daje tak ścisły praktyczny wynik.

Podsumowanie do tej pory

Tutaj jest to, co zostało udowodnione do tej pory:

1. Jeśli tablica mogłaby zaczynać się w dowolnej kolejności, w najgorszym przypadku potrzebne jest co najmniej O(NlogN)O(Nlog{N}) porównań
2. Średnia liczba porównań musi być co najmniej równa entropii tablicy, co jest O(NlogN)O(Nlog{N}) dla losowych danych wejściowych

Zauważ, że #2 pozwala algorytmom sortowania opartym na porównaniach być szybszym niż O(NlogN)O(Nlog{N}), jeśli dane wejściowe są niskiej entropii (innymi słowy, bardziej przewidywalne). Merge sort jest bliski O(N)O(N), jeśli dane wejściowe zawierają wiele posortowanych podtablic. Sortowanie przez wstawianie jest bliskie O(N)O(N), jeśli wejściem jest tablica, która została posortowana przed poddaniem jej pewnym zaburzeniom. Żaden z nich nie bije O(NlogN)O(Nlog{N}) w najgorszym przypadku, chyba że pewne uporządkowania tablicy są niemożliwe jako dane wejściowe.

Ogólne algorytmy sortowania

Sorty oparte na porównaniach są interesującym przypadkiem specjalnym w praktyce, ale nie ma nic teoretycznie specjalnego wCMP przeciwieństwie do jakiejkolwiek innej instrukcji na komputerze. Oba powyższe argumenty można uogólnić na dowolny algorytm sortowania, jeśli zwrócimy uwagę na kilka rzeczy:

1. Większość instrukcji komputerowych ma więcej niż dwa możliwe wyjścia, ale wciąż ich liczba jest ograniczona
2. Ograniczona liczba wyjść oznacza, że jedna instrukcja może przetworzyć tylko ograniczoną ilość entropii

Daje nam to ten sam O(NlogN)O(Nlog{N}) dolny limit na liczbę instrukcji. Każdy fizycznie realny komputer może przetwarzać ograniczoną liczbę instrukcji naraz, więc jest to również O(NlogN)O(Nlog{N}) dolne ograniczenie na wymagany czas.

Ale co z „szybszymi” algorytmami?

Najbardziej użyteczną praktyczną implikacją ogólnego O(NlogN)O(Nlog{N}) jest to, że jeśli słyszysz o jakimkolwiek asymptotycznie szybszym algorytmie, to wiesz, że musi on w jakiś sposób „oszukiwać”. Musi być jakiś haczyk, który oznacza, że nie jest to algorytm sortowania ogólnego przeznaczenia, który skaluje się do arbitralnie dużych tablic. Może to być nadal użyteczny algorytm, ale dobrze jest dokładnie przeczytać drobny druk.

Dobrze znanym przykładem jest sortowanie radix. Jest on często nazywany algorytmem sortującym O(N)O(N), ale haczyk polega na tym, że działa on tylko wtedy, gdy wszystkie liczby mieszczą się w kk bitach, a tak naprawdę jest to O(kN)O(kN).

Co to oznacza w praktyce? Załóżmy, że masz 8-bitową maszynę. Możesz reprezentować 28=2562^8 = 256 różnych liczb w 8 bitach, więc jeśli masz tablicę tysięcy liczb, będziesz miał haveduplicates. To może być w porządku dla niektórych aplikacji, ale dla innych trzeba uaktualnić do co najmniej 16 bitów, które mogą reprezentować 216=65,5362^16 = 65,536 liczb wyraźnie. 32 bity będą obsługiwać 232=4,294,967,2962^32 = 4,294,967,296 różnych liczb. Ponieważ rozmiar tablicy wzrasta, liczba potrzebnych bitów będzie miała tendencję do wzrostu, zbyt. Aby reprezentować NN różnych liczb w sposób wyraźny, będziesz potrzebował k≥log2Nk \geq \log_2{N}. Tak więc, chyba że jesteś w porządku z wieloma duplikatami w swojej tablicy, O(kN)O(kN) jest efektywnie O(NlogN)O(Nlog{N}).

Potrzeba O(NlogN)O(Nlog{N}) danych wejściowych w ogólnym przypadku faktycznie dowodzi ogólnego wyniku sama w sobie. Ten argument nie jest tak interesujący w praktyce, ponieważ rzadko potrzebujemy sortować miliardy liczb całkowitych na maszynie 32-bitowej, a jeśli ktoś trafił na ograniczenia maszyny 64-bitowej, nie powiedział o tym reszcie z nas.