ข้ามไปเนื้อหา

การวิเคราะห์แบบถัวเฉลี่ย

จากวิกิพีเดีย สารานุกรมเสรี

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

ประวัติ

[แก้]

วิธีการ

[แก้]

การใช้โดยทั่วไป

[แก้]

อ้างอิง

[แก้]
  • Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press. pp. 20, 141. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2006-10-05. สืบค้นเมื่อ 2012-12-03.
  1. Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2013-10-20, สืบค้นเมื่อ 2011-05-03
  2. สมชาย ประสิทธิ์จูตระกูล, การออกแบบและวิเคราะห์อัลกอริทึม, พิมพ์ครั้งที่ 4