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

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

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

Copyright