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