Co to jest amortyzowana analiza algorytmów? [Zamknięte]

Czym różni się od analizy asymptotycznej? Kiedy go używasz i dlaczego?

Przeczytałem kilka artykułów, które wydają się być dobrze napisane, na przykład te:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

ale nadal nie rozumiem w pełni tych pojęć.

Czy ktoś może mi to uprościć?

Analiza amortyzowana nie mnoży naiwnie liczby wywołań z najgorszym przypadkiem dla jednego wywołania.

Na przykład w przypadku tablicy dynamicznej, której rozmiar podwaja się w razie potrzeby, normalna analiza asymptotyczna wykazałaby tylko, że dodanie do niej elementu kosztuje O (n), ponieważ może być konieczne powiększenie i skopiowanie wszystkich elementów do nowej tablicy. Analiza zamortyzowana bierze pod uwagę, że aby musieć rosnąć, n / 2 pozycji musiało zostać dodanych bez powodowania wzrostu od poprzedniego wzrostu, więc dodanie pozycji zajmuje tak naprawdę tylko O ​​(1) (koszt O (n) wynosi amortyzowane ponad n / 2 działań).

Analiza amortyzowana to nie to samo, co „średnia wydajność” - analiza zamortyzowana daje twardą gwarancję tego, co się stanie, jeśli wykonasz tyle działań.

Jest wiele odpowiedzi na pytanie „co”, ale nie ma żadnej na pytanie „dlaczego”.

Jak wszyscy powiedzieli, analiza asymptotyczna dotyczy tego, jak wydajność danej operacji skaluje się do dużego zbioru danych. Analiza amortyzowana dotyczy tego, jak skaluje się średnia wyników wszystkich operacji na dużym zestawie danych. Analiza amortyzowana nigdy nie daje gorszych granic niż asymptotyczne, a czasami daje znacznie lepsze.

Jeśli obawiasz się całkowitego czasu pracy dłuższej pracy, prawdopodobnie zależy Ci na lepszych granicach amortyzowanej analizy. Dlatego języki skryptowe (na przykład) często chętnie powiększają tablice i tablice mieszające o jakiś czynnik, mimo że jest to kosztowna operacja. (Uprawa może być O(n)operacją, ale amortyzowana jest O(1)dlatego, że robisz to rzadko).

Jeśli programujesz w czasie rzeczywistym (poszczególne operacje muszą zostać zakończone w przewidywalnym czasie), wtedy lepsze granice amortyzowanej analizy nie mają znaczenia. Nie ma znaczenia, czy operacja była średnio szybka, czy nie udało się jej zakończyć na czas, aby wrócić i wyregulować piłę taśmową, zanim przecięła za daleko ...

To, co ma znaczenie w twoim przypadku, zależy dokładnie od tego, jaki jest twój problem programistyczny.

Analiza asymptotyczna

Termin ten odnosi się do analizy wydajności algorytmu przy założeniu, że dane, na których działa algorytm (dane wejściowe ), są, mówiąc laikiem, „na tyle duże, że powiększenie ich nie zmieni wniosku”. Chociaż dokładna wielkość wkładu nie musi być określona (musimy tylko górną granicę), dane postawiła sobie ma zostać określona.

Zwróć uwagę, że do tej pory rozmawialiśmy tylko o metodzie analizy; nie sprecyzowaliśmy, jaką dokładnie wielkość analizujemy (złożoność czasowa? złożoność przestrzeni?), ani nie określiliśmy, która miara nas interesuje (najgorszy przypadek? najlepszy przypadek? średnia?).

W praktyce termin analiza asymptotyczna powszechnie odnosi się do górnej granicy złożoności czasowej algorytmu, tj. Wydajności w najgorszym przypadku mierzonej całkowitym czasem wykonywania, który jest reprezentowany przez notację duże-Oh (np. Algorytm sortowania O(nlogn)).

Analiza zamortyzowana

Termin ten odnosi się do analizy wydajności algorytmu opartej na określonej sekwencji operacji, która jest ukierunkowana na najgorszy scenariusz - to znaczy, zamortyzowana analiza oznacza, że ​​metryka jest wydajnością w najgorszym przypadku (chociaż nadal nie mówi, która wielkość jest mierzona ). Aby wykonać tę analizę, musimy określić rozmiar danych wejściowych, ale nie musimy przyjmować żadnych założeń co do jego formy.

Mówiąc prościej, zamortyzowana analiza polega na wybieraniu dowolnego rozmiaru danych wejściowych, a następnie „przegrywaniu” algorytmu. Zawsze, gdy trzeba podjąć decyzję zależną od wkładu, obrana jest najgorsza ścieżka¹. Po zakończeniu działania algorytmu dzielimy obliczoną złożoność przez rozmiar danych wejściowych, aby otrzymać ostateczny wynik.

¹ Uwaga: Dokładniej mówiąc, najgorsza ścieżka, jaka jest teoretycznie możliwa . Jeśli masz wektor, który dynamicznie podwaja swój rozmiar za każdym razem, gdy jego pojemność się wyczerpie, „najgorszy przypadek” nie oznacza, że ​​będzie on musiał podwoić się po każdym wstawieniu, ponieważ wstawienia są przetwarzane jako sekwencja. Możemy (a nawet musimy) używać znanego stanu, aby matematycznie wyeliminować jak najwięcej „jeszcze gorszych” przypadków, nawet jeśli dane wejściowe pozostają nieznane.

Najważniejsza różnica

Krytyczna różnica między analizą asymptotyczną i amortyzowaną polega na tym, że pierwsza jest zależna od samego wejścia, podczas gdy druga jest zależna od sekwencji operacji, które wykona algorytm.

W związku z tym:

• Analiza asymptotyczna pozwala stwierdzić, że złożoność algorytmu, gdy otrzyma najlepsze / najgorsze / średnie dane wejściowe o wielkości zbliżającej się do N, jest ograniczona przez jakąś funkcję F (N) - gdzie N jest zmienną
• analiza zamortyzowana pozwala stwierdzić, że złożoność algorytmu, gdy otrzyma dane wejściowe o nieznanej charakterystyce, ale znanej wielkości N, nie jest gorsza niż wartość funkcji F (N) - gdzie N jest znaną wartością

Odpowiedź na to zwięźle definiuje pierwsze zdanie rozdziału Analiza zamortyzowana w książce - Wprowadzenie do algorytmów:

W analizie amortyzowanej czas wymagany do wykonania sekwencji operacji na strukturze danych jest uśredniany ze wszystkich wykonanych operacji.

Przedstawiamy złożoność rozwoju programu za pomocą analizy asymptotycznej - która polega na ograniczaniu wzrostu programu przez funkcję i określaniu najgorszego, najlepszego lub przeciętnego przypadku.

Ale może to być mylące w przypadkach, gdy istnieje tylko jeden przypadek, w którym złożoność programu osiąga szczyt, ale ogólnie program nie wymaga wielu obliczeń.

Dlatego bardziej sensowne jest uśrednianie kosztu w ramach sekwencji operacji, nawet jeśli pojedyncza operacja może być kosztowna. To jest analiza zamortyzowana!

Analiza zamortyzowana jest alternatywą dla techniki asymptotycznej używanej do obliczania złożoności. Pomaga nam obliczyć bardziej prawdziwą złożoność pod względem praktycznym, aby porównać i wybrać między dwoma lub więcej algorytmami.

Najlepsze odniesienie, jakie do tej pory znalazłem, aby zrozumieć zamortyzowaną analizę algorytmów, znajduje się w książce Wprowadzenie do algorytmów , wydanie trzecie, rozdział 17: „Analiza zamortyzowana”. To wszystko jest tam, wyjaśnione znacznie lepiej niż to, co można znaleźć w poście Stack Overflow. Książkę znajdziesz w bibliotece każdego porządnego uniwersytetu.

Regularna analiza asymptotyczna patrzy na wykonanie pojedynczej operacji asymptotycznie, jako funkcję rozmiaru problemu. Notacja O () jest tym, co wskazuje na analizę asymptotyczną.

Analiza zamortyzowana (która jest również analizą asymptotyczną) sprawdza całkowitą wydajność wielu operacji na współużytkowanej strukturze danych .

Różnica polega na tym, że zamortyzowana analiza zwykle dowodzi, że całkowite obliczenia wymagane dla operacji M mają lepszą gwarancję wydajności niż M razy najgorszy przypadek dla pojedynczej operacji.

Na przykład pojedyncza operacja na drzewie typu splay o rozmiarze N może zająć do O (N) czasu. Jednak sekwencja M operacji na drzewie o rozmiarze N jest ograniczona przez O (M (1 + log N) + N log N) czas, który w przybliżeniu wynosi O (log N) na operację. Należy jednak zauważyć, że analiza zamortyzowana jest znacznie bardziej rygorystyczna niż analiza „przeciętnego przypadku”: dowodzi, że każda możliwa sekwencja operacji spełni asymptotyczny najgorszy przypadek.

Analiza zamortyzowana dotyczy całkowitego kosztu w wielu przebiegach procedury i korzyści, jakie można z tego uzyskać. Na przykład wyszukiwanie nieposortowanej tablicy n elementów dla pojedynczego dopasowania może wymagać do n porównań, a zatem jest o (n) złożoności. Jeśli jednak wiemy, że ta sama tablica będzie przeszukiwana pod kątem m pozycji, powtórzenie całego zadania miałoby wówczas złożoność O (m * n). Jeśli jednak posortujemy tablicę z wyprzedzeniem, koszt wyniesie O (n log (n)), a kolejne wyszukiwania zajmą tylko O ​​(log (n)) dla posortowanej tablicy. Zatem całkowity zamortyzowany koszt dla m elementów przy tym podejściu wynosi O (n * log (n) + m * log (n)). Jeśli m> = n, to równa się O (n log (n)) przez sortowanie wstępne w porównaniu z O (n ^ 2) w przypadku braku sortowania. Dzięki temu zamortyzowany koszt jest tańszy.

Krótko mówiąc, wydając trochę więcej na początku, możemy dużo zaoszczędzić później.