นิยาม
ตามทฤษฎีความซับซ้อนทางการคำนวณ Potential Method เป็นวิธีที่ใช้วิเคราะห์ เวลาและพื้นที่แบบแอมอร์ไทซ์ (Amortized Time and Space Complexity) ของโครงสร้างข้อมูล – วัดประสิทธิภาพตลอดลำดับการดำเนินการที่กำจัดต้นทุนของการดำเนินการที่เกิดขึ้นนานแต่นานแต่มีค่าใช้จ่ายสูง
แนวคิดหลัก
ใน Potential Method จะเลือกฟังก์ชัน Φ (Phi) ที่แปลงสถานะของโครงสร้างข้อมูลเป็นจำนวนไม่ติดลบ
- หาก S เป็นสถานะของโครงสร้างข้อมูล Φ(S) แทนงานที่นับแล้วในการวิเคราะห์แอมอร์ไทซ์แต่ยังไม่ได้ทำจริง
- อาจจินตนาการได้ว่าเป็น พลังงานศักย์ (Potential Energy) ที่เก็บอยู่ในสถานะนั้น
- ก่อนเริ่มต้นโครงสร้างข้อมูล ค่า Potential ถูกกำหนดเป็นศูนย์
- หรือมองว่า Φ(S) แทน ความไม่เป็นระเบียบ (Disorder) ในสถานะ S หรือระยะห่างจากสถานะที่เหมาะสม
ตัวอย่าง
ให้ฟังก์ชันพื้นฐาน Φ บนสถานะของโครงสร้างข้อมูล ตอบสนองเงื่อนไข:
- Φ(a₀) = 0 โดยที่ a₀ คือสถานะเริ่มต้น
- Φ(aₜ) ≥ 0 สำหรับทุกสถานะ aₜ ที่เกิดขึ้นตลอดการคำนวณ
โดย 직관 (Intuition) ฟังก์ชันพื้นฐานจะติดตาม เวลาที่จ่ายล่วงหน้า (Precharged Time) ในจุดใดจุดหนึ่งของการคำนวณ วัดปริมาณเวลาที่เก็บไว้เพื่อจ่ายค่าใช้จ่ายการดำเนินการที่แพง – เหมือน ยอดเงินในธนาคาร (Banker's Method) แต่น่าสนใจที่มันขึ้นอยู่กับ สถานะปัจจุบันของโครงสร้างข้อมูลอย่างเดียว ไม่ขึ้นกับประวัติการคำนวณ
นิยามเวลาแอมอร์ไทซ์
เวลาแอมอร์ไทซ์ของการดำเนินการนิยามว่า:
c + Φ(a') – Φ(a)
โดยที่ c คือต้นทุนจริงของการดำเนินการ และ a, a' คือสถานะของโครงสร้างข้อมูลก่อนและหลังการดำเนินการตามลำดับ ดังนั้น เวลาแอมอร์ไทซ์ = เวลาจริง + การเปลี่ยนแปลงของ Potential
ในลักษณะที่เหมาะสม Φ ควรนิยามให้ เวลาแอมอร์ไทซ์ของแต่ละการดำเนินการเล็ก การเปลี่ยนแปลง Potential ควรเป็นบวกสำหรับการดำเนินการต้นทุนต่ำ และลบสำหรับการดำเนินการต้นทุนสูง
