Wyjaśnienie znaczenia asymptotycznej złożoności algorytmów w praktyce projektowania algorytmów

W algorytmach i złożoności skupiamy się na asymptotycznej złożoności algorytmów, tj. Ilości zasobów wykorzystywanych przez algorytm przy wielkości wejściowej do nieskończoności.

W praktyce potrzebny jest algorytm, który działałby szybko w skończonej (choć prawdopodobnie bardzo dużej) liczbie instancji.

Algorytm, który działa dobrze w praktyce na skończonej liczbie instancji, którymi jesteśmy zainteresowani, nie musi mieć dobrej złożoności asymptotycznej (dobra wydajność w skończonej liczbie instancji nie implikuje niczego w odniesieniu do złożoności asymptotycznej). Podobnie algorytm o dobrej złożoności asymptotycznej może nie działać dobrze w praktyce w skończonej liczbie instancji, którymi jesteśmy zainteresowani (np. Z powodu dużych stałych).

Dlaczego używamy asymptotycznej złożoności? Jak te asymptotyczne analizy odnoszą się do projektowania algorytmów w praktyce?

Ciekawe pytanie brzmi: jaka jest alternatywa? Jedyną inną znaną mi metodą jest testowanie / testy porównawcze. Programujemy algorytmy, pozwalamy im działać na (reprezentatywnej próbce) skończonego zestawu danych wejściowych i porównywać wyniki. Jest z tym kilka problemów.

• Wyniki nie są ogólne pod względem maszyn. Uruchom test porównawczy na innym komputerze, a na pewno uzyskasz różne wyniki, ilościowo, a może nawet jakościowo.
• Wyniki nie są ogólne pod względem języków programowania. Różne języki mogą powodować bardzo różne wyniki.
• Wyniki nie są ogólne pod względem szczegółów realizacji. Dosłownie porównujesz programy , a nie algorytmy; niewielkie zmiany we wdrożeniu mogą powodować ogromne różnice w wydajności.
• Jeśli najgorszy przypadek jest rzadki, losowa próbka wejściowa może nie zawierać złej instancji. Jest to sprawiedliwe, jeśli obawiasz się o średnią wydajność przypadku, ale niektóre środowiska wymagają gwarancji najgorszego przypadku.
• W praktyce zmieniają się zestawy danych wejściowych. Zazwyczaj nakłady stają się z czasem większe. Jeśli nie będziesz powtarzać testu porównawczego co sześć miesięcy (tak, niektóre dane rosną tak szybko), Twoje wyniki wkrótce będą bezwartościowe¹.

To powiedziawszy, ignorowanie wszelkiego rodzaju efektów i stałych w analizie jest typowe, ale można je nazwać leniwym (w odniesieniu do praktyki). Służy on do porównywania pomysłów algorytmicznych bardziej niż do wskazywania wydajności danej (nawet pseudokodu) implementacji. Społeczność jest dobrze znana, że ​​jest to gruboziarniste i że często konieczne jest bliższe przyjrzenie się; na przykład Quicksort jest mniej wydajny niż sortowanie wstawiania dla (bardzo) małych nakładów. Szczerze mówiąc, dokładniejsza analiza jest zwykle trudna ².

Innym, a posteriori uzasadnieniem formalnego, abstrakcyjnego punktu widzenia jest to, że na tym poziomie rzeczy są często wyraźniejsze. Tak więc dziesięciolecia badań teoretycznych przyniosły wiele algorytmicznych pomysłów i struktur danych, które są przydatne w praktyce. Teoretycznie optymalny algorytm nie zawsze jest tym, którego chcesz użyć w praktyce - należy wziąć pod uwagę inne względy, ale wydajność; pomyśl o kupach Fibonacciego - a ta etykieta może nawet nie być wyjątkowa. Dla typowego programisty zajmującego się optymalizacją wyrażeń arytmetycznych trudno jest wymyślić nowy pomysł na tym poziomie (nie mówiąc już, że tak się nie dzieje); jednak może (i powinna) przeprowadzić te optymalizacje w oparciu o zasymilowany pomysł.

Istnieją formalne, teoretyczne narzędzia, aby w pewnym stopniu wypełnić lukę w praktyce. Przykładami są

• biorąc pod uwagę hierarchię pamięci (i inne wejścia / wyjścia),
• analiza średniego przypadku (w stosownych przypadkach),
• analizowanie liczby pojedynczych wyciągów (zamiast abstrakcyjnych miar kosztów) i
• wyznaczanie stałych czynników.

Na przykład Knuth jest znany z dosłownego liczenia liczby różnych instrukcji (dla danej implementacji w danym modelu), co pozwala na precyzyjne porównanie algorytmów. Takie podejście jest niemożliwe na poziomie abstrakcyjnym i trudne do wykonania w bardziej złożonych modelach (myślę Java). Zobacz [4] dla nowoczesnego przykładu.

Zawsze będzie luka między teorią a praktyką. Aktualnie pracujemy nad narzędziem³, którego celem jest połączenie najlepszych rozwiązań z obu światów, aby uzyskać prognozy dźwiękowe zarówno dla kosztów algorytmu, jak i czasu działania (średnio), ale jak dotąd nie udało nam się wyeliminować scenariuszy, w których jeden algorytm ma wyższy kosztuje, ale krótszy czas działania (na niektórych komputerach) niż równoważny (chociaż możemy to wykryć i pomóc znaleźć przyczynę).

Zalecam praktykom stosowanie teorii do filtrowania przestrzeni algorytmów przed uruchomieniem testów porównawczych:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

1. Mogą wystąpić szalone zmiany w wydajności bezwzględnej i względnej, gdy wzrośnie liczba braków pamięci podręcznej, co zwykle ma miejsce, gdy liczba danych wejściowych rośnie, ale maszyna pozostaje taka sama.
2. Jak w tej chwili czołowi badacze w tej dziedzinie nie są w stanie tego zrobić.
3. Znajdź narzędzie tutaj . Przykładowe zastosowanie zostało opublikowane w dziale inżynierii Java 7 Dual Pivot Quicksort Using MaLiJAn przez S. Wilda i in. (2012) [ przedruk ]
4. Analiza średnich przypadków podwójnego obrotu Quicksort Java 7 przez S. Wilda i M. Nebela (2012) - [ przedruk ]

Zakładam, że to pytanie wynika z nauczania kursu, który obejmuje analizę asymptotyczną. Istnieje kilka możliwych odpowiedzi na pytanie, dlaczego ten materiał jest nauczany na zajęciach wprowadzających:

• Analiza asymptotyczna jest matematyczną abstrakcją, która poddaje się analizie. Jako (prawdopodobnie) matematycy, chcemy być w stanie analizować algorytmy, a oni tylko w celu oswojenia ich złożoności wykorzystują analizę asymptotyczną.

• Ocena asymptotycznej wydajności algorytmu wskazuje pewne zasady przydatne w praktyce: na przykład skoncentruj się na tej części kodu, która zajmuje większość czasu, i zdyskontuj każdą część kodu, która zajmuje asymptotycznie nieistotną część czasu .

• Przydatne są niektóre techniki analizy asymptotycznej. Mam tu na myśli głównie tak zwane „twierdzenie mistrza”, które w wielu okolicznościach jest dobrym opisem rzeczywistości.

• Istnieje również powód historyczny: kiedy ludzie po raz pierwszy zaczęli analizować algorytmy, szczerze myśleli, że asymptotyczna złożoność odzwierciedla praktyczne zastosowanie. Jednak ostatecznie okazały się one błędne. To samo stało się z P jako klasą problemów, które można skutecznie rozwiązać, a NP jako klasą nierozwiązywalnych problemów, które w praktyce wprowadzają w błąd.

Osobiście uważam, że analiza asymptotyczna jest rozsądną częścią programu nauczania. Bardziej wątpliwe są teoria języka formalnego i teoria złożoności (wszystko, co ma związek z maszyną Turinga). Niektórzy twierdzą, że chociaż tematy te nie są przydatne dla przyszłego programisty, to wpajają jej pewne myśli, które są niezbędne, aby być dobrym praktykiem. Inni twierdzą, że teoria czasami wpływa na praktykę, a te rzadkie przypadki są wystarczające, aby uzasadnić nauczanie tych dość tajemniczych przedmiotów ogółowi informatyki. Wolałbym, żeby uczyli się historii lub literatury lub jakiegokolwiek innego przedmiotu, którym byliby naprawdę zainteresowani; oba są równie istotne dla ich przyszłych perspektyw pracy i ważniejsze dla nich, jak ludzi.

Istnieją dwa poważne powody, dla których warto zastosować asymptotyczną analizę czasów pracy:

• $n$

• aby umożliwić matematyczną wykonalność. Przypadki takie, że można znaleźć dokładne wyrażenia dla liczby operacji, są wyjątkowe. Badanie asymptotyków otwiera więcej możliwości (przydatne są asymptotyczne aproksymacje skomplikowanych funkcji).

I jest wiele innych (takich jak niezależność maszyny, znaczenie, porównywalność ...).

Jak zauważono w odpowiedzi Raphaela, dokładne obliczenie najgorszego przypadku może być bardzo trudne. Dokładne obliczenia mogą być również niepotrzebne, ponieważ model pamięci RAM już wprowadza przybliżenia. Na przykład, czy wszystkie operacje naprawdę zajmują tyle samo czasu? Określone implementacje (sprzęt, optymalizacje) mogą przyspieszyć algorytm ze względu na stałe czynniki. Chcemy zrozumieć, jak skuteczny jest algorytm niezależny od tych czynników. Jest to duża motywacja do zastosowania analizy asymptotycznej.

Ponieważ asymptotyki są „proste” (cóż, w każdym razie prostsze niż dokładna analiza przypadków skończonych).

Porównaj np. Encyklopedyczną „Sztukę programowania komputerowego” Knutha, która dokonuje szczegółowej analizy wszystkich ważnych algorytmów (i wielu nie tak ważnych) z analizą praktyczną, która często wystarcza, aby uzyskać asymptotyczne oszacowanie ( lub po prostu związany), jak praktykowano w większości książek o „algorytmach”.

Z pewnością masz rację. Jeśli problem jest wystarczająco ważny, uzasadniona może być analiza w stylu Knutha (lub może nieco mniej szczegółowa). W wielu przypadkach wystarczy wskazówka na temat asymptotycznej złożoności (być może średniej z dyspersją) dopasowanej do danych eksperymentalnych. W większości przypadków , aby dokonać zgrubnej klasyfikacji konkurencyjnych algorytmów, pierwsza runda eliminacji porównująca asymptotyki może być wystarczająco precyzyjna. A jeśli nie ma konkurentów, otrzymywanie złej wiadomości o dokładnym koszcie w najdrobniejszych szczegółach jest tylko masochizmem.

Tutaj poprzez analizę asymptotyczną zakładam, że mamy na myśli zachowanie algorytmu, gdy wielkość danych wejściowych przechodzi w nieskończoność.

Powodem, dla którego stosujemy analizę asymptotyczną jest to, że jest ona przydatna w przewidywaniu zachowania algorytmów w praktyce . Prognozy pozwalają nam podejmować decyzje, np. Kiedy mamy różne algorytmy dla problemu, którego należy użyć? (Bycie użytecznym nie oznacza, że ​​zawsze jest poprawne).

To samo pytanie można zadać na temat dowolnego uproszczonego modelu świata rzeczywistego. Dlaczego używamy uproszczonych modeli matematycznych realnego świata?

Pomyśl o fizyce. Klasyczna fizyka newtonowska nie jest tak dobra jak fizyka relatywistyczna w przewidywaniu świata rzeczywistego. Ale jest to wystarczająco dobry model do budowy samochodów, wieżowców, łodzi podwodnych, samolotów, mostów itp. Są przypadki, w których nie jest wystarczająco dobry, np. Jeśli chcemy zbudować satelitę lub wysłać sondę kosmiczną do Plutona lub przewidzieć ruch masywnych obiektów niebieskich, takich jak gwiazdy i planety, lub obiektów o bardzo dużej prędkości, takich jak elektrony. Ważne jest, aby wiedzieć, jakie są granice modelu.

1. Zazwyczaj jest to wystarczająco dobre przybliżenie realnego świata. W praktyce często widzimy, że algorytm z lepszą analizą asymptotyczną działa lepiej w praktyce. Rzadko zdarza się, że algorytm ma lepsze zachowanie asymptotyczne. Więc jeśli dane wejściowe mogą być wystarczająco duże, wówczas zazwyczaj możemy polegać na analizie asymptotycznej jako pierwszej prognozie zachowania algorytmów. Nie jest tak, jeśli wiemy, że nakłady będą niewielkie. W zależności od wymaganej wydajności możemy potrzebować dokładniejszej analizy, np. Jeśli mamy informacje o rozkładzie danych wejściowych, otrzymamy algorytm, możemy przeprowadzić dokładniejszą analizę, aby osiągnąć wyznaczone cele (np. Szybko na 99 % nakładów). Chodzi o to, że analiza asymptotyczna pierwszego kroku jest dobrym punktem wyjścia. W praktyce powinniśmy również przeprowadzać testy wydajności, ale należy pamiętać, że ma to również swoje własne problemy.

2. $A$$A$$A$ma lepszą asymptotyczną złożoność. Które z nich nie są lepsze od innych we wszystkich danych wejściowych? To staje się trudniejsze i zależy od tego, na czym nam zależy. Czy zależy nam na dużych nakładach czy małych nakładach? Jeśli zależy nam na dużych nakładach, nie jest powszechne, że algorytm ma lepszą złożoność asymptotyczną, ale zachowuje się gorzej na dużych wejściach, na których nam zależy. Jeśli bardziej zależy nam na małych nakładach, analiza asymptotyczna może nie być tak przydatna. Powinniśmy porównać czas działania algorytmów na wejściach, na których nam zależy. W praktyce w przypadku skomplikowanych zadań o skomplikowanych wymaganiach analiza asymptotyczna może nie być tak przydatna. W przypadku prostych podstawowych problemów, które opisują podręczniki algorytmów, jest to całkiem przydatne.

Krótko mówiąc, złożoność asymptotyczna jest względnie łatwym do obliczenia przybliżeniem faktycznej złożoności algorytmów dla prostych podstawowych zadań (problemy w podręczniku algorytmów). Gdy budujemy bardziej skomplikowane programy, wymagania dotyczące wydajności zmieniają się i stają się bardziej skomplikowane, a analiza asymptotyczna może nie być tak przydatna.

Warto porównać analizę asymptotyczną z innymi podejściami do przewidywania wydajności algorytmów i ich porównywania. Jednym z powszechnych podejść są testy wydajności w odniesieniu do danych losowych lub danych porównawczych. Jest to powszechne, gdy obliczanie złożoności asymptotycznej jest trudne lub niewykonalne, np. Gdy używamy heurystyki, jak na przykład rozwiązywania SAT. Kolejny przypadek ma miejsce, gdy wymagania są bardziej skomplikowane, np. Gdy wydajność programu zależy od czynników zewnętrznych, a naszym celem może być posiadanie czegoś, co kończy się w pewnych ustalonych terminach (np. Pomyśl o aktualizacji interfejsu pokazanego użytkownikowi) na 99% wejścia.

Pamiętaj jednak, że analiza wydajności ma również swoje problemy. Nie zapewnia on matematycznych dotacji na wydajność, ponieważ w rzeczywistości uruchamiamy test wydajności na wszystkich danych wejściowych, które zostaną podane algorytmowi (często nie do obliczenia) (i często nie jest możliwe zdecydowanie, że niektóre dane wejściowe nigdy nie zostaną podane). Jeśli testujemy na przeciwko próbie losowej lub benchmarku jesteśmy niejawnie zakładając pewne prawidłowości dotyczące wykonywania algorytmów, czyli algorytm wykona podobnie na innych środków, które nie były częścią testu wydajności.

Drugi problem z testami wydajności polega na tym, że zależą one od środowiska testowego. Tzn. Wydajność programu nie zależy od samych danych wejściowych, ale od czynników zewnętrznych (np. Typ maszyny, system operacyjny, wydajność kodowanego algorytmu, wykorzystanie procesora, czasy dostępu do pamięci itp.), Z których niektóre mogą się różnić w zależności od różnych przebiegów test na tej samej maszynie. Ponownie zakładamy, że określone środowiska, w których przeprowadzany jest test wydajności, są podobne do rzeczywistego środowiska, chyba że wykonujemy testy wydajności we wszystkich środowiskach, w których możemy uruchomić program (i jak możemy przewidzieć, na jakich komputerach ktoś może uruchomić sortowanie algorytm włączony za 10 lat?).

$\Theta(n \lg n)$$\Theta(n^2)$$\Theta(\lg n)$$O(n)$

$O(n^2)$$O(n \log n)$$O(n^2)$ aby zakończyć w porównaniu do Quicksort.

wyobraź sobie teraz, że czekanie powtarzane jest w kodzie tyle razy, ile wywoływany jest kod. jak matematycznie kwantyfikować / uzasadnić tę pozorną wyższość algorytmu szybkiego sortowania? (tj. czy jego nazwa jest naprawdę uzasadniona, czy to tylko hasło marketingowe?) poprzez asymptotyczne pomiary złożoności. patrzy się subiektywnie na animacje, czując, że bąbelki są słabszym algorytmem, a asymptotyczna analiza złożoności może to udowodnić ilościowo. Należy jednak pamiętać, że analiza złożoności asymptotycznej jest tylko jednym narzędziem w zestawie narzędzi do analizy algorytmów i nie zawsze jest ostateczna.

i warto również przyjrzeć się kodowi side-by-side. bubbleort wydaje się być koncepcyjnie prostszy i nie używa rekurencji. quicksort nie jest tak od razu rozumiany, szczególnie w przypadku zasady „mediana 3”. bubbleort może być zaimplementowany tylko w pętlach bez podprogramu, podczas gdy quicksort może zazwyczaj mieć co najmniej jeden podprogram. pokazuje to wzorzec, że większe wyrafinowanie kodu może czasem poprawić asymptotyczną złożoność kosztem prostoty kodu. czasami dochodzi do skrajnego kompromisu podobnego do koncepcji malejących zysków krańcowych (pochodzących z ekonomii), w których bardzo duże ilości złożoności kodu [wymagające uzasadnienia całych dokumentów pełnych thms i dowodów] kupują tylko bardzo małe ulepszenia w asymptotycznej złożoności. pokazuje się to jako przykład espmnożenie macierzy, a nawet wykresy .