Ukryte stałe w złożoności algorytmów

W przypadku wielu problemów algorytm o największej złożoności asymptotycznej ma bardzo duży stały współczynnik, który jest ukryty przez dużą notację O. Dzieje się tak w przypadku mnożenia macierzy, mnożenia liczb całkowitych (w szczególności najnowszego algorytmu mnożenia liczb całkowitych O (n log n) Harveya i van der Hoevena), sieci sortowania o małej głębokości i znajdowania drobnych wykresów, aby zrobić kilka. Takie algorytmy są czasami nazywane algorytmami galaktycznymi.

Należy pamiętać, że w przypadku innych algorytmów, takich jak ogólne sortowanie i dodawanie liczb całkowitych, algorytmy są znane z optymalnej złożoności asymptotycznej i małych stałych czynników.

Jakie badania przeprowadzono w celu oddzielenia wcześniejszych algorytmów od drugich z perspektywy teoretycznej?

Wiem, że często pomija się ukryte stałe, aby ukryć rozróżnienie między różnymi modelami obliczeń. Jestem jednak przekonany, że przy wielu różnych modelach te algorytmy galaktyczne będą wolniejsze niż na przykład asymptotycznie gorsze algorytmy dla danych wejściowych wielkości jednego miliarda. W niektórych przypadkach rozróżnienie nie jest subtelne. Czy stało się to rygorystyczne?

Na przykład można wymyślić bardzo prosty model obliczeń, taki jak maszyna von Neumanna z bardzo prostym ISA, a następnie zaimplementować algorytmy i powiązać ich czas działania z wyraźnymi stałymi. Czy zostało to zrobione dla różnych algorytmów?

Ciekawym podejściem do pewnej klasy algorytmów i problemów kombinatorycznych jest kombinatoryka analityczna . Główne opisane podejście jest podobne do tego, co sugerujesz: zaczynasz od konkretnej implementacji algorytmu i identyfikujesz powtarzające się operacje (zwykle najcięższe), których użyjesz do powiązania jawnie policzalnej złożoności dla wykonania danych wejściowych danego rozmiar$N$ w postaci liczby $C_N$ wybrana operacja jest wykonywana.

Metodologia nie wymaga naprawy żadnego konkretnego modelu obliczeń, chociaż może to oczywiście być przydatne. Zauważ też, że możesz spróbować obliczyć najgorsze zachowanie lub oczekiwane zachowanie, lub coś jeszcze.

Najważniejszym składnikiem tej metodologii jest analiza funkcji generujących te wartości. Czasami można uzyskać bardzo dokładne asymptotyczne aproksymacje za pomocą metod z kompleksowej analizy.

Prostym przykładem opisanym w książce jest szybki przegląd. Ma to kwadratowy najgorszy czas działania, ale w praktyce przewyższa większość$\mathcal O(n\log n)$algorytmy. Dokonując dokładnej analizy oczekiwanego kosztu Quicksort i porównując go do Scalanie, widzisz, że oczekuje się, że przewyższy ten drugi rozmiar około 10, jeśli dobrze pamiętam. Aby móc obliczyć tego rodzaju rzeczy, nie można oczywiście pominąć ukrytych stałych.

W rzeczywistości w szybkim sortowaniu sortujesz listę, rekurencyjnie sortując listy podrzędne, dzięki czemu uzyskasz poprawę dla wszystkich rozmiarów, jeśli użyjesz scalania na listach mniejszych niż rozmiar 10. Ciekawa uwaga w książce wspomina, że ​​w niektórych bibliotekach Microsoft o otwartym źródle, algorytm sortowania ogólnego jest implementowany jako szybkie sortowanie, dopóki nie dojdziesz do rozmiaru 10, po czym zostanie użyty scalanie. W komentarzach do kodu wspomniano, że testy wydajności wykazały, że ta wartość jest optymalna.