ამორტიზებული ანალიზი ზომავს საშუალო খরჭს ოპერაციის პერ თანმიმდევრობით, მაშინაც კი, თუ ინდივიდუალური ოპერაციები ზოგჯერ ბევრად მეტი ღირს. ეს ხსნის, თუ რატომ არის დინამიური მასივის append "O(1) ამორტიზებული" მიუხედავად ზოგჯერ O(n) ზომის შეცვლებისა.
თუ დინამიური მასივი სავსე ხდება, ის ყოს ახალი მასივი (ჩვეულებრივ ) და ყველა ელემენტს კოპირებს — O(n) ნაბიჯი. მაგრამ რადგან სიმძლავრე , ძვირადღირი კოპიები ექსპონენციალურად იშვიათხდება.
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
| ოპერაცია | ხელიერი ერთი | ამორტიზებული |
|---|---|---|
| append (იორმაგება) | O(n) | O(1) |
ზრდა მუდმივი ოდენობით ჩააქცევდა თითოეულ შეტანას ასლების ტრიგერად, რაც O(n) ამორტიზებულს მისცემდა. გამრავლებითი ზრდა არის ის, რაც ხარჯს გაშლის.
ამორტიზებული ანალიზი იძლევა სამართლიან, რეალისტურ სახეს მუშაობისა — მის გარეშე, თქვენ არასწორად შეშინდებოდით, რომ ყოველი append ან ჰეშ-ცხრილის შეტანა არის O(n).
ის ასევე დაამტკიცებს საკვანძო დიზაინის წესს: გაზარდოთ სიმძლავრე გამრავლებით, რომელიც აყრილია დინამიური მასივებში, ჰეშ-ცხრილებში და სტრიქონის შემქმნელებში ყველგან.