Uchambuzi wa amortized hupima wastani wa gharama kwa operesheni juu ya mlolongo, hata kama operesheni za mtu binafsi mara kwa mara huvuta zaidi. Inaeleza kwa nini append ya safu ya nguvu ni "O(1) amortized" licha ya kubadili O(n) mara kwa mara.
Jinsi safu ya nguvu inapokataa, inakamatia safu mpya (kawaida ) na kunakili vipengele vyote — hatua ya O(n). Lakini kwa sababu uwezo , kunakili ghali kunakuwa nadra kwa njia ya kielelezo.
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
| Operesheni | Kesi mbaya zaidi | Amortized |
|---|---|---|
| append (kuzaliana) | O(n) | O(1) |
Kukua kwa kiasi kisichobadilika kingefanya kila kuingiza kutakabiri kunakili, kuwa na O(n) amortized. Ukuaji wa kuzidisha ndio unayosaambaa gharama.
Uchambuzi wa amortized inatoa picha ya haki, halisi ya utendaji — bila yake, ungefanya kosa kwa kuhofu kwamba kila append au kuingiza kwa jedwali la hash ni O(n).
Inakamatia pia kanuni muhimu ya muundo: ukuaji wa kuzidisha wa uwezo, ambayo ni msingi wa safu za nguvu, meza za hash na wajenzi wa kamba kila mahali.