การวิเคราะห์เวลาการทำงาน

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

วัตถุประสงค์

เพื่อให้ผู้เรียนสามารถ

•  อธิบายขั้นตอนการวิเคราะห์เวลาการทำงานเชิงเส้นกำกับ
•  เปรียบเทียบอัตราการเติบโตของฟังก์ชันต่าง ๆ
•  นิยามสัญกรณ์เชิงเส้นกำกับ
•  วิเคราะห์อัลกอริทึมเชิงเส้นกำกับ