Amortized Analysis คืออะไร?
ใช้เมื่อ การดำเนินการบางครั้งช้ามาก แต่ ส่วนใหญ่เร็ว ต้องการวิเคราะห์ต้นทุนเฉลี่ย ต้องใช้ใน Hash Tables, Disjoint Sets เป็นต้น
Hash Table: Search/Insert ส่วนใหญ่ O(1) แต่เมื่อ Collision → O(n) สำหรับ Collision Resolution
Aggregate Method
หาต้นทุนรวม สำหรับ n การดำเนินการ:
Amortized Cost = Cost(n operations) / n
= (Cost(normal) + Cost(expensive)) / n
ตัวอย่าง: Dynamic Array
Insert ที่ Index มีอยู่ → O(1) แต่ถ้า Index ไม่มี → Double Array Size แล้ว Insert
ให้ cᵢ = ต้นทุนการแทรกครั้งที่ i
cᵢ = 1 + { i-1, if i-1 is power of 2
{ 0, otherwise
Amortized Cost:
Σcᵢ / n ≤ (n + Σ2ʲ) / n = O(n) / n = O(1)
โดย j = 1 ถึง ⌊log₂(n-1)⌋
