วิธีที่เป็นไปได้

ตามทฤษฎีความซับซ้อนในการคำนวณ วิธีการที่เป็นไปได้ถูกกำหนดให้เป็นวิธีการที่ใช้ในการวิเคราะห์เวลาและความซับซ้อนของพื้นที่ตัดจำหน่ายของโครงสร้างข้อมูล ซึ่งเป็นการวัดประสิทธิภาพการทำงานเหนือลำดับการดำเนินการที่ช่วยลดต้นทุนของการดำเนินการที่ไม่บ่อยแต่มีราคาแพง

ในวิธีที่เป็นไปได้ ฟังก์ชัน Φ จะถูกเลือกเพื่อแปลงสถานะของโครงสร้างข้อมูลเป็นตัวเลขที่ไม่เป็นลบ ถ้า S เป็นสถานะของโครงสร้างข้อมูล Φ(S) หมายถึงงานที่รวมอยู่ในการวิเคราะห์ค่าตัดจำหน่ายแต่ยังไม่ได้ดำเนินการ ดังนั้น Φ(S) อาจถูกจินตนาการว่าเป็นการคำนวณปริมาณพลังงานศักย์ที่เก็บไว้ในสถานะนั้น ก่อนที่จะเริ่มต้นโครงสร้างข้อมูล ค่าที่เป็นไปได้ถูกกำหนดให้เป็นศูนย์ อีกทางหนึ่ง Φ(S) อาจถูกจินตนาการว่าเป็นตัวแทนของจำนวนความผิดปกติในสถานะ S หรือระยะห่างจากสภาวะในอุดมคติ

ตัวอย่าง

ให้เราสามารถแสดงฟังก์ชันที่เป็นไปได้ Φ (อ่าน "พี") ในสถานะของโครงสร้างข้อมูลที่มีคุณสมบัติดังต่อไปนี้ -

• Φ(a0) =0 โดยที่ a0 คือสถานะเริ่มต้นของโครงสร้างข้อมูล
• Φ(at) ≥ 0 สำหรับทุกสถานะที่โครงสร้างข้อมูลที่เกิดขึ้นในขณะที่ทำการคำนวณ

ตามสัญชาตญาณ ฟังก์ชันที่เป็นไปได้จะสามารถติดตามเวลาที่ชาร์จไว้ล่วงหน้า ณ จุดใดก็ได้ในการคำนวณ มันวัดจำนวนเวลาที่ประหยัดได้เพื่อจ่ายสำหรับการดำเนินงานที่มีราคาแพง ก็เหมือนยอดเงินในธนาคารตามวิธีของนายธนาคาร แต่สิ่งที่น่าสนใจก็คือ ขึ้นอยู่กับสถานะปัจจุบันของโครงสร้างข้อมูลเท่านั้น ไม่ว่าประวัติของการคำนวณจะอยู่ในสถานะนั้นอย่างไร

จากนั้นเราจะกำหนดเวลาตัดจำหน่ายของการดำเนินการเป็น

c + Φ(a') − Φ(a),

โดยที่ c คือต้นทุนดั้งเดิมของการดำเนินการ และ a และ a' คือสถานะของโครงสร้างข้อมูลก่อนและหลังการดำเนินการ ตามลำดับ ดังนั้นเวลาที่ตัดจำหน่ายจึงถูกกำหนดเป็นเวลาจริงบวกกับการเปลี่ยนแปลงในศักยภาพ ตามหลักการแล้ว Φ ควรกำหนดเพื่อให้เวลาตัดจำหน่ายของการดำเนินการแต่ละครั้งมีขนาดเล็ก ดังนั้น การเปลี่ยนแปลงศักยภาพควรวัดเป็นบวกสำหรับการดำเนินการต้นทุนต่ำ และค่าลบสำหรับการดำเนินการต้นทุนสูง