Amortyzowana analiza? (Gwarancje wydajności najgorszego przypadku)

Co to jest analiza amortyzowana? I w jaki sposób może pomóc mi osiągnąć gwarancje najgorszego działania w moich programach?

Byłem przeczytaniu , że następujące techniki mogą pomóc programista osiągnąć najgorszym przypadku gwarancji wydajności (tj własnymi słowami: gwarancję, że czas pracy programu nie przekroczy czas pracy w najgorszym cast):

• Algorytmy randomizowane (np. Algorytm szybkiego sortowania jest w najgorszym przypadku kwadratowy, ale losowe uporządkowanie danych wejściowych daje probabilistyczną gwarancję, że czas działania jest liniowo-rytmiczny)
• Sekwencje operacji (nasza analiza musi uwzględniać zarówno dane, jak i sekwencję operacji wykonywanych przez klienta)
• Analiza amortyzowana (innym sposobem zapewnienia gwarancji wydajności jest amortyzacja kosztów poprzez śledzenie całkowitego kosztu wszystkich operacji podzielonego przez liczbę operacji. W tym ustawieniu możemy zezwolić na niektóre kosztowne operacje, przy jednoczesnym zachowaniu średniego kosztu niskich operacji. Innymi słowy, rozkładamy koszt kilku kosztownych operacji, przypisując ich część do każdej z wielu niedrogich operacji)

Autor wspomniał o zmianie rozmiaru struktury danych tablicowych dla Stack jako jednym z przykładów, jak osiągnąć amortyzowaną analizę, ale nadal nie rozumiem, co to jest amortyzowana analiza i jak można ją faktycznie zaimplementować (algorytm struktury danych?), Aby osiągnąć najgorsze - gwarancje wydajności emisji

Nie wdrażasz analizy zamortyzowanej. Jest to technika uzyskiwania dokładniejszych Ogranic.

Najważniejszą obserwacją, którą musisz poczynić, jest to, że kosztowne operacje nie mogą się nigdy zdarzyć.

W przypadku struktury danych opartej na macierzy, tablica wymaga zmiany rozmiaru co jakiś czas - kiedy jest pełna. Jest to najdroższa operacja i zajmuje dużo O(n)czasu. Wszystkie inne wstawki do tablicy są O(1).

Aby określić środowisko wykonawcze do wstawiania nelementów, można pomnożyć nje przez najdroższą operację O(n), co powoduje ogólne zachowanie środowiska wykonawczego na poziomie O(n^2).

Jest to jednak niedokładne, ponieważ zmiana rozmiaru nie może odbywać się zbyt często.

Mówiąc o pieniądzach, amortyzujesz koszty, kiedy spłacasz dług kilkoma niewielkimi płatnościami w czasie.

Możemy użyć tego modelu również do myślenia o algorytmach. Po prostu zastępujemy „czas” „pieniędzmi”, aby uniknąć mentalnego mapowania.

Po zapełnieniu tablicy do jej długości nmożemy podwoić jej rozmiar. Musimy wykonać następujące operacje:

• Przydziel 2nfragmenty pamięci
• kopiuj nelementy

Jeśli założymy, że zarówno przydzielanie pamięci, jak i kopiowanie odbywa się w czasie liniowym, będzie to bardzo kosztowna operacja. Możemy jednak teraz wykorzystać pomysł długu i amortyzować go do naszych analiz. Tylko, że spłacimy nasz dług, zanim go faktycznie spłacimy.
Załóżmy, że nasze saldo (pieniędzy / czasu) powraca do zera (tzn. Nie mamy długu ani żadnych resztek) po zmianie rozmiaru tablicy.

Ma to następujące implikacje:

• Wstawienie kolejnych nelementów pokryje koszt zmiany rozmiaru i kopiowania (użyliśmy ngniazd i nnieużywanych gniazd)

Możemy teraz pomyśleć o tym, ile każda operacja wstawiania musi zapłacić:

• Wkładka
• Koszt przydzielenia jednego fragmentu pamięci
• koszt przeniesienia go do nowo przydzielonej pamięci

Pokryliśmy teraz koszty alokacji pamięci, kopiowania i wstawiania kolejnych nelementów. Jednak zaniedbaliśmy jeszcze przydzielanie miejsca dla starych nelementów, a także ich kopiowanie.

Po prostu rozdzielamy koszty naszych starych nelementów na nasze nowe (jeszcze do wstawienia) nelementy:

• Koszt przydzielenia jednego fragmentu pamięci
• koszt przeniesienia go do nowo przydzielonej pamięci

W sumie każda operacja wstawiania będzie kosztować 5 jednostek. Opłaca się to za własne wstawianie oraz przenoszenie i przydzielanie miejsca dla siebie i jednego ze starych elementów.

Każda operacja wstawiania nadal trwa przez cały czas, ale zmiana rozmiaru odbywa się za darmo: amortyzujemy ją, poświęcając „więcej” czasu na każdą wstawkę.

W rezultacie wstawianie nelementów wymaga O(n)czasu.

Inne techniki analizy zamortyzowanej są wyjaśnione tutaj .

Po pierwsze: Jest to technika analizy środowisk uruchomieniowych programu, a nie technika implementacji algorytmów.

Przykład wymieniony na liście jest dobry: Dołączanie pojedynczego elementu do struktury danych opartej na tablicy. W przypadku każdej operacji dołączania najgorszym przypadkiem jest skopiowanie wszystkich istniejących elementów. Tego rodzaju analiza jest zbyt pesymistyczna, ponieważ nie musisz tego robić, jeśli używasz rozsądnej strategii zmiany rozmiaru (pomnożenie rozmiaru przez niektóre x> 1,0). Analiza następnie stwierdza, że ​​masz granicę O (n ^ 2) - O (n) na element razy n elementów - podczas gdy rzeczywisty czas działania wynosi tylko O ​​(n).

Jeśli uśredniasz koszt zmiany rozmiaru dla wszystkich wstawionych elementów (z których większość nie wymaga zmiany rozmiaru), przeprowadzana jest amortyzowana analiza. Amortyzowana analiza powoduje powstanie granicy O (n), która odpowiada rzeczywistemu zachowaniu algorytmu.