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

40

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?

Kaveh
źródło
Kolejnym istotnym pytaniem jest: dlaczego ignorujemy stałe czynniki ?
Raphael

Odpowiedzi:

24

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 ]
Raphael
źródło
3
Prawdopodobnie czysty akt studiowania teorii algorytmów wyostrzy twoje oko i wytrenuje twój mózg abstrakcyjny w zakresie algorytmów, dając ci kolejne narzędzie do oceny kodu w codziennym programowaniu. Abstrahuj od kodu, oceniaj zasadę, ulepszaj ją i tłumacz z powrotem na kod. Przykład: „Ach, rozumiem, chcesz zaprogramować słownik. Ale zasadniczo programujesz listy; dlaczego nie spróbować drzew?”
Raphael
Granice analizy asymptotycznej stają się oczywiste po głębszym kopaniu; Quicksort jest znakomitym przykładem .
Raphael
1
FWIW, napisałem nawet bliższy migawkę moich opinii na temat notacji Landau tutaj .
Raphael
11

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.

Yuval Filmus
źródło
Dzięki Yuval. Motywacja jest głównie zainteresowana tym, w jaki sposób wyjaśnić uczniom przydatność analizy asymptotycznej i jej znaczenie dla praktyki projektowania i stosowania algorytmów w rzeczywistych aplikacjach (gdzie przez większość czasu jest jasne, że interesuje nas tylko skończone, choć możliwe bardzo duża liczba przypadków), nie usprawiedliwiające programu nauczania.
Kaveh
1
Jestem zaskoczony twoją przesłanką. Wydaje się, że grupą docelową są zarówno matematycy, jak i początkujący programiści, co jest dziwną kombinacją i żadna z nich nie charakteryzuje informatyków. (Poza tym nie podzielam twojego zdania na temat języków formalnych, ale to inny temat.)
Raphael
Przeciwnie, zakładam, że grupą docelową są początkujący programiści. Jednak większość programu nauczania jest dostępna ze względu na teoretycznych informatyków. Oczywiście te dwie grupy mają sprzeczne potrzeby. Ponieważ większość studentów to potencjalni programiści, uważam, że program powinien być skierowany do nich, ale niektórzy naukowcy nie zgadzają się z tym. Być może chcą uczyć przyszłych profesorów. Może możesz wyjaśnić ich punkt widzenia.
Yuval Filmus
3
@YuvalFilmus Często wyjaśniałem, że nie wierzę, że CS = Programowanie TCS +. Jeśli uczysz kursu CS (na uniwersytecie) i większość twoich studentów chce zostać programistami, coś jest zepsute (imho). Twierdziłbym, że każdy informatyk może skorzystać z solidnego wykształcenia w zakresie algorytmiki, języków formalnych, a nawet teorii złożoności (i wielu innych rzeczy, takich jak działanie kompilatorów i procesorów).
Raphael
2
@Wildcard Architektura komputera, grafika komputerowa, sztuczna inteligencja, badania języków programowania, ... - lista jest nieskończona! TCS jest naprawdę niszą, a programowanie jest jedynie narzędziem dla (większości) badaczy CS.
Raphael
7

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ść ...).

Yves Daoust
źródło
n
Cóż, nie sądzę, że to w ogóle reguła. Im więcej danych wyrzucasz, tym słabsze są wypowiedzi. Perspektywa asymptotyczna (a tym bardziej „wielka”) tworzy takie stwierdzenia, jak „Quicksort jest szybszy niż Insertionsort”, co, jeśli nie fałszywe, nie jest do końca prawdą. (Tak, mówię, że analiza algorytmu jest często nauczana źle, imho.)
Raphael
6

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.

Juho
źródło
3

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.

vonbrand
źródło
2
To tylko połowa prawdy: po pierwsze, wydaje się, że piszesz z myślą o „big-oh” (o czym pytanie nie wspomina). Po drugie, asymptotyki o „wielkiej och” są znane z tego, że spektakularnie ponoszą porażkę w przypadku „eliminacji” podczas wybierania algorytmów: dane wejściowe są w rzeczywistości skończone.
Raphael
3

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. AAAma 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?).

Θ(nlgn)Θ(n2)Θ(lgn)O(n)

Kaveh
źródło
Podoba mi się ta odpowiedź, aby głosować teraz. Dwie uwagi: 1) Użyłbym tutaj „kosztu” zamiast „złożoności”. Częściowo z powodów do wkurzenia, ale także dlatego, że istnieje wiele możliwych miar kosztów (co komplikuje wszystkie wymienione przez ciebie względy). 2) Możesz zrobić karnet na język polski. ;)
Raphael
@Raphael, dzięki. Wkrótce planuję kolejną edycję. :)
Kaveh
-2

O(n2)O(nlogn)O(n2) 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 .

vzn
źródło
Istnieje wiele obszarów między „oglądaniem animacji” a analizami formalnymi, takimi jak obszerne testy porównawcze środowiska uruchomieniowego. W rzeczywistości są one własnym ważnym obszarem, ponieważ nie mamy teorii wyjaśniającej wszystkie rzeczy, które mają wpływ na środowiska wykonawcze.
Raphael
@ raphael w swojej odpowiedzi obejmowałeś testy porównawcze; to dobra odpowiedź. ale zauważ, że animacja / wizualizacja może być ściśle związana z testami porównawczymi. faktycznie istnieje wiele wyjaśnień na temat tego, co wpływa na środowisko uruchomieniowe [ujęte w innych odpowiedziach], ale do pewnego stopnia jego „szum” i asymptotyczna złożoność „wygładza / uśrednia hałas”. to kolejne ćwiczenie, aby zobaczyć, jak to faktycznie robi.
vzn
Animacje nie odfiltrowują hałasu. Co więcej, ludzkie oko jest łatwe do oszukiwania i po prostu nie jest możliwe oglądanie animacji dla rozsądnej wielkości próbki list o rozsądnych rozmiarach (powiedzmy, 1000 list dla rozmiarów w milionach do algorytmów sortowania) i zdecydować, który algorytm był szybszy (średnio).
Raphael
nn
n