Bəzi əməliyyatlar çox vaxt ucuzdur, amma nadir hallarda bahalı olur. Ən pis halı hər əməliyyata ayrıca tətbiq etsək, nəticə həddindən artıq pessimist çıxır. Amortizə analizi əməliyyatlar ardıcıllığının ümumi qiymətini götürüb onu əməliyyatların sayına bölür.
Dinamik massiv: list.append
Siyahı massivdə saxlanılır. Yer qurtaranda yeni, daha böyük massiv ayrılır və bütün elementlər köçürülür — bu O(n)-dir. Lakin tutumu hər dəfə iki dəfə artırsaq, köçürmələr nadir olur: 1 + 2 + 4 + ... + n/2 < n. n append-in ümumi qiyməti n (özü) + < n (köçürmə) = O(n), yəni bir append amortizə olaraq O(1)-dir.
class DynArray:
def __init__(self):
self.cap = 1
self.size = 0
self.data = [None]
self.copies = 0
def append(self, x):
if self.size == self.cap: # full: allocate twice as much
self.cap *= 2
new = [None] * self.cap
for i in range(self.size):
new[i] = self.data[i]
self.copies += 1
self.data = new
self.data[self.size] = x
self.size += 1