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
źródło