Amortizovaný čas je způsob vyjádření časové složitosti, kdy algoritmus má kromě časové složitosti, která se vyskytuje většinu času, velmi špatnou časovou složitost jen jednou za čas. Dobrým příkladem může být ArrayList, což je datová struktura, která obsahuje pole a může být rozšířena. Další definice ze Stack Overflow je průměrný čas potřebný na jednu operaci, pokud se provádí mnoho operací.
Když ArrayList narazí na kapacitu pole v něm, pak vytvoří nové pole s dvojnásobnou velikostí starého pole a zkopíruje všechny položky ve starém poli do nového pole. V ArrayListu existují dvě časové složitosti; jedna je O(1) a druhá je O(n).
Když pole v něm nedosáhlo své kapacity a stále má dostatek místa pro vkládání položek
Pro vložení položky do pole v tomto případě stačí vložit položku za poslední položku. Stále máme místo pro vkládání položek.
Když pole v něm dosáhlo své kapacity a potřebuje se znovu vytvořit s dvojnásobnou velikostí
Pole dosáhlo kapacity a nemáme žádné volné sloty. Pak musíme vytvořit zcela nové pole se zdvojenou velikostí. A pak zkopírovat položky ve starém do nového, což zabere O(n), kde n je kapacita starého pole a nejhorší případ.
Pro vyjádření těchto dvou časových složitostí je zde amortizovaný čas. Jeho účelem je umožnit nám popsat nejhorší případ, který se stane jednou za čas pokaždé, když vnitřní pole narazí na svou kapacitu.
Ale jednou se to stane a nebude se to opakovat tak dlouho, aby se náklady „amortizovaly“. (Cracking the Coding Interview 6. vydání 43)
Jak tedy popíšeme obě složitosti?
V případě ArrayListu můžeme říci, že
vložení trvá O(n), když bylo dosaženo kapacity, a amortizovaný čas pro každé vložení je O(1).
Buďme však přesní pro nejhorší časovou složitost bez zjednodušení tohoto času. Pokud vnitřní kapacita pole začíná hodnotou 1, pak kapacity budou 1, 2, 4, 8, 16… X, když dosáhne kapacity a zdvojnásobí se. Kopírování do nového pole trvá 1, 2, 4, 8 16… X položek v závislosti na dosažené kapacitě. Takže časová složitost bude 1 + 2 + 4 + 8 + 16 +… X. Pokud budete uvažovat od X, bude to X + X/2 + X/4 + X/8… + 1 = přibližně 2X. Takže jinými slovy přesně,
vložení trvá O(2X), když bylo dosaženo kapacity X, a amortizovaný čas pro každé vložení je O(1).
.
