Amortized time jest sposobem wyrażenia złożoności czasowej, gdy algorytm ma bardzo złą złożoność czasową tylko raz na jakiś czas oprócz złożoności czasowej, która zdarza się przez większość czasu. Dobrym przykładem byłaby ArrayList, która jest strukturą danych, która zawiera tablicę i może być rozszerzona. Inna definicja ze Stack Overflow to średni czas potrzebny na operację, jeśli wykonujesz wiele operacji.
Gdy ArrayList trafia w pojemność tablicy w nim, wtedy tworzy nową tablicę z podwojonym rozmiarem starej tablicy i kopiuje wszystkie elementy w starej tablicy do nowej tablicy. W ArrayList istnieją dwie złożoności czasowe; jedna to O(1), a druga to O(n).
Gdy tablica w niej nie osiągnęła swojej pojemności i wciąż ma wystarczająco dużo miejsca na wstawianie elementów
Aby wstawić element do tablicy w tym przypadku, musimy po prostu umieścić element za ostatnim elementem. Nadal mamy miejsce na wstawianie elementów.
Gdy tablica w niej osiągnęła swoją pojemność i musi się ponownie utworzyć z podwojonym rozmiarem
Tablica osiągnęła pojemność i nie mamy wolnych slotów. Następnie musimy utworzyć zupełnie nową tablicę z podwojonym rozmiarem. A następnie skopiować elementy w starej do nowej, co zajmuje O(n), gdzie n jest pojemnością starej tablicy i najgorszym przypadkiem.
Aby wyrazić te dwie złożoności czasowe, czas amortyzowany jest tutaj. To, co robi, to pozwolić nam opisać najgorszy przypadek zdarza się raz na jakiś czas za każdym razem, gdy wewnętrzna tablica uderzyła w swoją pojemność.
Ale jeden zdarza się, nie zdarzy się ponownie przez tak długo, że koszt jest „zamortyzowany”. (Cracking the Coding Interview 6th edition 43)
Jak więc opisujemy te dwie złożoności?
W przypadku ArrayList możemy powiedzieć, że
Wstawianie trwa O(n), gdy pojemność została osiągnięta, a zamortyzowany czas dla każdego wstawienia wynosi O(1).
Ale bądźmy dokładni dla najgorszej złożoności czasowej bez upraszczania tego czasu. Jeśli wewnętrzna pojemność tablicy zaczyna się od 1, to pojemności będą wynosić 1, 2, 4, 8, 16… X, gdy trafi na pojemność i zostanie podwojona. Potrzeba 1, 2, 4, 8 16… X elementów do skopiowania do nowej tablicy w zależności od pojemności, która została osiągnięta. Więc złożoność czasowa będzie 1 + 2 + 4 + 8 + 16 +… X. Jeśli myślisz od X, będzie to X + X/2 + X/4 + X/8… + 1 = 2X w przybliżeniu. Więc innymi słowy dokładnie,
Wstawianie trwa O(2X), gdy pojemność X została osiągnięta, a zamortyzowany czas dla każdego wstawienia wynosi O(1).
.
