Analiza zamortyzowana mierzy średni koszt operacji na sekwencji, nawet gdy poszczególne operacje czasami kosztują znacznie więcej. Wyjaśnia, dlaczego append tablicy dynamicznej jest "O(1) zamortyzowane" pomimo sporadycznych zmian rozmiaru O(n).
Kiedy tablica dynamiczna się zapełni, przydziela nową tablicę (zwykle ) i kopiuje wszystkie elementy — krok O(n). Ale ponieważ pojemność się , drogie kopie stają się wykładniczo rzadsze.
Appending into a doubling array (cap shown):
ops: 1 2 3 4 5 6 7 8 9
cap: 1 2 4 4 8 8 8 8 16
copy: * * * * * <- copies at 1,2,4,8,16...
To insert n elements, total copy work =
1 + 2 + 4 + ... + n ≈ 2n (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
arr = []
for i in range(1_000_000):
arr.append(i) # almost always O(1); rarely O(n) during a resize
| Operacja | Najgorszy pojedynczy | Zamortyzowane |
|---|---|---|
| append (podwajanie) | O(n) | O(1) |
Wzrost o stałą wartość spowodowałby, że każde wstawienie wywoła kopię, dając O(n) zamortyzowane. Wzrost multiplikatywny to właśnie rozprzestrzenianie kosztów.
Analiza zamortyzowana daje uczciwy, realistyczny obraz wydajności — bez niej błędnie obawiałbyś się, że każde append lub wstawienie do tablicy mieszającej to O(n).
Justyfikuje także kluczową zasadę projektowania: zwiększaj pojemność multiplikatywnie, która stanowi podstawę tablic dynamicznych, tablic mieszających i konstruktorów ciągów znaków wszędzie.
Biblioteka pytań rekrutacyjnych IT ze szczegółowymi odpowiedziami — od Juniora do Seniora.
Wesprzyj