ความท้าทายในการคำนวณต้นทุนแอมอร์ไทซ์
การคำนวณต้นทุนแบบแอมอร์ไทซ์ (Amortized Cost) ของการดำเนินการ Meld เป็นงานที่ท้าทาย ความยากหลักอยู่ที่การคำนวณสะสมสำหรับความแตกต่างที่กว้างขวางของต้นทุนการดำเนินการที่ทำที่จุดต่างๆ ในลำดับการดำเนินการแบบสุ่ม
แม้เป้าหมายการออกแบบจะได้รับผลกระทบจากต้นทุนของลำดับการดำเนินการ แต่นิยามแนวคิดต้นทุนแอมอร์ไทซ์ของการดำเนินการในรูปของต้นทุนลำดับการดำเนินการนำไปสู่ข้อสรุปที่ไม่ได้อะไร
ฟังก์ชันพื้นฐาน (Potential Function) – วิธีแก้ปัญหา
การนำ ฟังก์ชันพื้นฐาน (Potential Function) มาใช้เพื่อชดเชยความแปรปรวนของต้นทุนจริงเป็นวิธีที่เหมาะสมในการจัดการสถานการณ์นี้
นิยามทางคณิตศาสตร์
ให้ B เป็นชนิดข้อมูลนามธรรม (Abstract Data Type - ADT) ที่มีการดำเนินการพื้นฐาน P = {P₁, P₂, ..., Pₖ} และให้ DS เป็นโครงสร้างข้อมูลที่นำ B ไปใช้
ให้ F เป็นฟังก์ชันพื้นฐานที่ระบุบนคอนฟิกูเรชันของโครงสร้างข้อมูลไปยังจำนวนจริงที่ไม่ติดลบ ให้เพิ่มเติมว่า F(Φ) = 0 ให้ DSʲ ระบุคอนฟิกูเรชันที่ได้หากเราทำการดำเนินการ Pₖ บนคอนฟิกูเรชัน DS และให้ C แทนต้นทุนจริงของการทำ Pₖ บน DS
ดังนั้น ต้นทุนแอมอร์ไทซ์ของ Pₖ ที่ทำงานบน DS ซึ่งแทนด้วย a(Pₖ, DS) กำหนดโดย:
a(Pₖ, DS) = C + F(DSʲ) – F(DS)
หาก a(Pₖ, DS) ≤ c·g(m) สำหรับคอนฟิกูเรชัน DS ทุกคอนฟิกูเรชันที่มีขนาด m เราจึงสรุปได้ว่าต้นทุนแอมอร์ไทซ์ของ Pₖ เป็น O(g(m))
