Amortized Analysis (การวิเคราะห์ Amortized)
ใช้เมื่อการดำเนินการบางครั้งช้ามาก แต่ส่วนใหญ่ที่ทำบ่อยเร็ว โครงสร้างข้อมูลที่ต้องการ: Hash Tables, Disjoint Sets
ใน Hash Table การค้นหาส่วนใหญ่ O(1) แต่บางครั้ง O(n) เมื่อเกิด Collision ต้องใช้ O(n) แก้ไข
Aggregate Method (วิธีรวมค่า)
หาค่าใช้จ่ายรวม สำหรับลำดับ n การดำเนินการ Amortized Cost คือ:
ตัวอย่าง: Dynamic Array
แทรกข้อมูลที่ดัชนีที่กำหนด O(1) แต่ถ้าดัชนีไม่มี จะขยายอาร์เรย์เป็น 2 เท่าก่อน แล้วค่อยแทรก
ให้ cᵢ = ต้นทุนการแทรกครั้งที่ i
