Stały amortyzowany czas

Co rozumie się przez „Constant Amortized Time”, gdy mówimy o złożoności czasowej algorytmu?

Amortyzowany czas objaśniony prostymi słowami:

Jeśli wykonujesz operację, powiedz milion razy, tak naprawdę nie obchodzi Cię najgorszy przypadek lub najlepszy przypadek tej operacji - liczy się to, ile czasu zajmie całkowite powtórzenie operacji milion razy .

Nie ma więc znaczenia, czy operacja jest bardzo powolna raz na jakiś czas, o ile „raz na jakiś czas” jest na tyle rzadkie, że powolność może zostać osłabiona. Zasadniczo amortyzowany czas oznacza „średni czas potrzebny na operację, jeśli wykonujesz wiele operacji”. Amortyzowany czas nie musi być stały; możesz mieć liniowo i logarytmicznie amortyzowany czas lub cokolwiek innego.

Weźmy przykład maty dynamicznej tablicy, do której wielokrotnie dodajesz nowe elementy. Zwykle dodanie elementu zajmuje stały czas (to znaczy O(1)). Ale za każdym razem, gdy tablica jest pełna, alokujesz dwa razy więcej miejsca, kopiujesz dane do nowego regionu i zwalniasz stare miejsce. Zakładając, że przydziały i zwolnienia przebiegają w stałym czasie, ten proces powiększania wymaga O(n)czasu, gdzie n jest bieżącym rozmiarem tablicy.

Za każdym razem, gdy powiększasz, zajmuje to około dwa razy więcej czasu niż ostatnie powiększenie. Ale czekałeś też dwa razy dłużej! Koszt każdego rozszerzenia można zatem „rozłożyć” na wstawki. Oznacza to, że w długim okresie całkowity czas potrzebny na dodanie m elementów do tablicy wynosi O(m), a więc i amortyzowany czas (tj. Czas na wprowadzenie) wynosi O(1).

Oznacza to, że z czasem najgorszym scenariuszem będzie domyślnie O (1) lub stały czas. Typowym przykładem jest tablica dynamiczna. Jeśli już przydzieliliśmy pamięć dla nowego wpisu, dodanie jej będzie O (1). Jeśli go nie przydzieliliśmy, zrobimy to, przydzielając powiedzmy dwa razy bieżącą kwotę. Tym konkretnym wstawieniem nie będzie O (1), ale coś innego.

Ważne jest to, że algorytm gwarantuje, że po sekwencji operacji drogie operacje zostaną zamortyzowane, a tym samym renderowanie całej operacji O (1).

Lub ściślej,

Istnieje stała c, taka, że ​​dla każdej sekwencji operacji (także jednej kończącej się kosztowną operacją) o długości L czas nie jest większy niż c * L (Dzięki Rafał Dowgird )

Aby opracować intuicyjny sposób myślenia o tym, rozważ wstawienie elementów do tablicy dynamicznej (na przykład std::vectorw C ++). Narysujmy wykres, który pokazuje zależność liczby operacji (Y) potrzebnych do wstawienia N elementów w tablicy:

Pionowe części czarnego wykresu odpowiadają realokacji pamięci w celu rozszerzenia tablicy. Widzimy tutaj, że tę zależność można z grubsza przedstawić w postaci linii. A to równanie liniowe jest Y=C*N + b( Cjest stałe, bw naszym przypadku = 0). Dlatego możemy powiedzieć, że musimy wydać C*Nśrednio operacje na dodanie N elementów do tablicy lub C*1operacje na dodanie jednego elementu (zamortyzowany stały czas).

Uznałem, że poniższe wyjaśnienie Wikipedii jest użyteczne po trzykrotnym przeczytaniu:

Źródło: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

„Tablica dynamiczna

Amortyzowana analiza operacji wypychania dla tablicy dynamicznej

Rozważ dynamiczną tablicę, która powiększa się wraz z dodawaniem do niej większej liczby elementów, takich jak ArrayList w Javie. Gdybyśmy zaczęli od dynamicznej tablicy o rozmiarze 4, zajęłoby to cały czas, aby wcisnąć na nią cztery elementy. Jednak pchnięcie piątego elementu na tę tablicę zajęłoby więcej czasu, ponieważ tablica musiałaby utworzyć nową tablicę o podwójnym rozmiarze obecnego rozmiaru (8), skopiować stare elementy na nową tablicę, a następnie dodać nowy element. Kolejne trzy operacje push zajmowałyby podobnie stały czas, a następnie kolejne dodawanie wymagałoby kolejnego powolnego podwojenia wielkości tablicy.

Ogólnie biorąc, jeśli weźmiemy pod uwagę dowolną liczbę wypychań n do tablicy o rozmiarze n, zauważymy, że operacje wypychania wymagają stałego czasu, z wyjątkiem ostatniego, który zajmuje czas O (n) do wykonania operacji podwojenia wielkości. Ponieważ wykonano n operacji łącznie, możemy wziąć średnią z tego i przekonać się, że do wypychania elementów na tablicę dynamiczną potrzeba: O (n / n) = O (1), stały czas. ”

W moim rozumieniu jako prosta historia:

Załóżmy, że masz dużo pieniędzy. I chcesz je ułożyć w stos. I masz długie ręce i nogi, tyle ile potrzebujesz teraz lub w przyszłości. I musisz wypełnić wszystko w jednym pokoju, więc łatwo go zamknąć.

Idź prosto do końca / rogu pokoju i zacznij układać je w stosy. Gdy układasz je w stos, powoli w pokoju zabraknie miejsca. Jednak po wypełnieniu łatwo było je ułożyć w stos. Mam pieniądze, włóż pieniądze. Łatwy. To O (1). Nie musimy przenosić żadnych poprzednich pieniędzy.

Gdy w pokoju zabraknie miejsca. Potrzebujemy innego pokoju, który jest większy. Tutaj jest problem, ponieważ możemy mieć tylko 1 pokój, więc możemy mieć tylko 1 zamek, musimy przenieść wszystkie istniejące pieniądze z tego pokoju do nowego większego pokoju. Więc przenieś wszystkie pieniądze z małego pokoju do większego. Oznacza to, że ułóż je wszystkie ponownie. Tak więc, musimy przenieść wszystkie poprzednie pieniądze. Więc to jest O (N). (zakładając, że N jest całkowitą liczbą pieniędzy z poprzednich pieniędzy)

Innymi słowy, było łatwo do N, tylko 1 operacja, ale kiedy musimy przenieść się do większego pokoju, wykonaliśmy N. operacji. Innymi słowy, jeśli uśrednimy, to jest 1 wkładka na początku i 1 dodatkowy ruch podczas przeprowadzki do innego pokoju. Łącznie 2 operacje, jedna wkładka, jeden ruch.

Zakładając, że N jest duży jak 1 milion, nawet w małym pomieszczeniu, 2 operacje w porównaniu z N (1 milion) nie są tak naprawdę porównywalną liczbą, więc uważa się je za stałe lub O (1).

Zakładając, że wykonamy wszystkie powyższe czynności w innym większym pokoju i znów musimy się przenieść. To jest wciąż to samo. powiedzmy, N2 (powiedzmy 1 miliard) to nowa ilość pieniędzy w większym pokoju

Mamy więc N2 (który obejmuje N poprzedniego, ponieważ przenosimy wszystkie z małego do większego pokoju)

Nadal potrzebujemy tylko 2 operacji, jedna jest włożona do większego pokoju, a następnie kolejna operacja przeniesienia, aby przenieść się do jeszcze większego pomieszczenia.

Tak więc, nawet dla N2 (1 miliard), są to 2 operacje dla każdego. co znowu jest niczym. Jest więc stały lub O (1)

Tak więc, gdy N wzrasta z N do N2, lub innych, nie ma to większego znaczenia. Nadal jest stały lub operacje O (1) są wymagane dla każdego z N.

Załóżmy teraz, że masz N jako 1, bardzo mały, liczba pieniędzy jest niewielka, i masz bardzo mały pokój, który zmieści tylko 1 liczbę pieniędzy.

Gdy tylko wypełnisz pieniądze w pokoju, pokój jest pełny.

Kiedy idziesz do większego pokoju, załóż, że zmieści się w nim tylko jedno dodatkowe pieniądze, łącznie 2 liczby pieniędzy. Oznacza to, że poprzedni przeniósł pieniądze i jeszcze 1. I znowu jest wypełniony.

W ten sposób N rośnie powoli i nie jest już stałym O (1), ponieważ przenosimy wszystkie pieniądze z poprzedniego pokoju, ale możemy zmieścić tylko 1 dodatkowy pieniądze.

Po 100-krotności nowy pokój zmieści 100 pieniędzy z poprzedniego i 1 więcej pieniędzy, które może pomieścić. To jest O (N), ponieważ O (N + 1) to O (N), to znaczy stopień 100 lub 101 jest taki sam, oba są setkami, w przeciwieństwie do poprzedniej historii, od milionów do miliardów, a do miliardów .

Jest to więc nieefektywny sposób przydzielania pokoi (lub pamięci / pamięci RAM) na nasze pieniądze (zmienne).

Tak więc dobrym sposobem jest przydzielenie większej ilości miejsca z potęgami 2.

Rozmiar pierwszego pokoju = pasuje na 1 liczbę pieniędzy
Rozmiar drugiego pokoju = mieści 4 liczbę pieniędzy
3 rozmiar pokoju = pasuje 8 ilość pieniędzy
Rozmiar 4 pokoju = pasuje 16 ilość pieniędzy
5 rozmiar pokoju = pasuje 32 ilość pieniędzy
6 rozmiar pokoju = pasuje 64 ilość pieniędzy
7. wielkość pokoju = mieści 128 ilość pieniędzy
8. wielkość pokoju = pasuje 256 ilość pieniędzy
9. wielkość pokoju = pasuje 512 ilość pieniędzy
10. wielkość pokoju = pasuje 1024 ilość pieniędzy
11. wielkość pokoju = pasuje 2.048 ilość pieniędzy
. ..
16. rozmiar pokoju = pasuje do 65 536 liczby pieniędzy
...
32 rozmiar pokoju = pasuje do 4 294 967 296 liczby pieniędzy
...
64 rozmiar pokoju = pasuje do 18 446,744,073,709,551,616 liczby pieniędzy

Dlaczego to jest lepsze? Ponieważ na początku wygląda on powoli, a później szybciej, to znaczy w porównaniu do ilości pamięci w naszej pamięci RAM.

Jest to pomocne, ponieważ w pierwszym przypadku, chociaż jest to dobre, łączna ilość pracy do wykonania na pieniądze jest stała (2) i nieporównywalna z wielkością pokoju (N), pomieszczenie, które wzięliśmy na początkowych etapach, może być zbyt duży (1 milion), który może nie być w pełni wykorzystany, w zależności od tego, czy w pierwszym przypadku możemy uzyskać tyle pieniędzy, aby w ogóle zaoszczędzić.

Jednak w ostatnim przypadku, moc 2, rośnie w granicach naszej pamięci RAM. I tak, zwiększając moc 2, zarówno analiza Zmotoryzowana pozostaje stała i jest przyjazna dla ograniczonej pamięci RAM, którą mamy dzisiaj.

Powyższe objaśnienia dotyczą analizy agregatów, która polega na przyjęciu „średniej” z wielu operacji. Nie jestem pewien, w jaki sposób odnoszą się one do metody Bankersa lub fizykalnej metody amortyzacji.

Teraz. Nie jestem do końca pewny poprawnej odpowiedzi. Miałoby to jednak związek z podstawowym warunkiem obu metod fizyków + bankiera:

(Suma zamortyzowanego kosztu operacji)> = (Suma rzeczywistego kosztu operacji).

Główna trudność, z jaką się spotykam, polega na tym, że biorąc pod uwagę fakt, że zamortyzowane koszty asymptotyczne operacji różnią się od kosztów normalnie asymptotycznych, nie jestem pewien, jak ocenić znaczenie kosztów zamortyzowanych.

Wtedy ktoś podaje mój zamortyzowany koszt, wiem, że to nie to samo, co normalny koszt asymptotyczny. Jakie zatem wnioski wyciągnę z zamortyzowanego kosztu?

Ponieważ mamy do czynienia z nadmiernym obciążeniem niektórych operacji, podczas gdy inne są zaniżone, jedną hipotezą może być to, że cytowanie zamortyzowanych kosztów poszczególnych operacji byłoby bez znaczenia.

Na przykład: w przypadku stosu fibonacciego wycenę zamortyzowanego kosztu samego Klucza Zmniejszającego na O (1) jest bez znaczenia, ponieważ koszty są redukowane przez „pracę wykonaną przez wcześniejsze operacje zwiększania potencjału stosu”.

LUB

Moglibyśmy przyjąć następującą hipotezę uzasadniającą koszty zamortyzowane:

1. Wiem, że kosztowna operacja będzie poprzedzona operacjami WIELU NISKICH KOSZTÓW.

2. Dla celów analizy zamierzam przeciążyć niektóre tanie operacje, TAKIE, ŻE ICH KOSZT ASYMPTOTYCZNY NIE ZMIENIA SIĘ.

3. Dzięki tym zwiększonym kosztom operacji mogę udowodnić, że kosztowna operacja ma MNIEJSZY KOSZT ASYMPTOTYCZNY.

4. W ten sposób poprawiłem / zmniejszyłem ASYMPTOTIC-BOUND kosztu n operacji.

Zatem analiza zamortyzowanego kosztu + limity zamortyzowanego kosztu mają teraz zastosowanie tylko do kosztownych operacji. Tanie operacje mają taki sam koszt asymptotyczny zamortyzowany jak ich normalny koszt asymptotyczny.

Wydajność dowolnej funkcji można uśrednić, dzieląc „całkowitą liczbę wywołań funkcji” przez „całkowity czas wszystkich wykonanych wywołań”. W ten sposób można uśrednić nawet funkcje, które trwają coraz dłużej dla każdego wykonywanego połączenia.

Zatem istotą funkcji, która wykonuje, Constant Amortized Timejest to, że ten „średni czas” osiąga pułap, którego nie można przekroczyć w miarę zwiększania liczby połączeń. Każde połączenie może różnić się wydajnością, ale w dłuższej perspektywie ten średni czas nie będzie coraz większy.

Jest to podstawowa zaleta czegoś, co działa Constant Amortized Time.