การวิเคราะห์ขั้นตอนวิธี

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

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

การวิเคราะห์ขั้นตอนวิธีทางทฤษฎีเป็นวิธีการปกติที่ใช้ประเมินความซับซ้อนของมันเมื่อพิจารณาประสิทธิภาพของขั้นตอนวิธีกับชุดข้อมูลที่มีขนาดใหญ่มาก เช่น ประมาณฟังก์ชันความซับซ้อนสำหรับอินพุตขนาดใหญ่ใด ๆ สัญกรณ์โอใหญ่ (Big O notation) สัญกรณ์โอเมก้า และสัญกรณ์ธีต้า (theta notation) ถูกใช้เพื่อการนี้ด้วย ตัวอย่างเช่น การทำงานสำหรับการค้นหาแบบทวิภาคเท่ากับจำนวนของขั้นตอนสัมพันธ์กับลอการิทึมของความยาวของรายการที่ต้องการค้นหา หรือ O (log (n)) หรือกว่าว่า "ในเวลาลอการิทึม" โดยปกติการประเมินประสิทธิภาพของขั้นตอนวิธีมักใช้กับข้อมูลขนาดใหญ่มาก ๆ เนื่องจากการดำเนินการที่แตกต่างกันของขั้นตอนวิธีเดียวกันอาจมีประสิทธิภาพต่างกัน อย่างไรก็ตามประสิทธิภาพของการดำเนินการอย่างมีเหตุผลสองวิธีของขั้นตอนวิธีที่ให้เกี่ยวข้องกันโดยปัจจัยตัวคูณคงที่ที่เรียกว่าค่าคงที่แฝง (Hidden factor)

การวัดประสิทธิภาพอย่างแม่นยำ บางครั้งสามารถคำนวณได้ แต่มันต้องการสมมติฐานที่แน่นอนเกี่ยวกับการดำเนินการเป็นพิเศษของขั้นตอนวิธี เรียกว่าโมเดลของการคำนวณ ซึ่งอาจนิยามในเทอมของ คอมพิวเตอร์นามธรรม เช่น เครื่องจักรทัวริง และ/หรือ โดยการสมมุติว่าการดำเนินการที่แน่นอนถูกกระทำในเวลาหนึ่งหน่วย ตัวอย่างเช่น การค้นหาอิลีเมนต์จากรายการที่จัดเรียงแล้ว (Sorted list) n อิลีเมนต์ ด้วยวิธีค้นหาแบบทวิภาค และเราสามารถรับประกันว่าการค้นหาอิลีเมนต์แต่ละครั้งทำในเวลาหนึ่งหน่วย ดังนั้นคำตอบที่ได้จะใช้เวลาในการค้นหาอย่างมากที่สุดเท่ากับ log₂ n + 1 หน่วยเวลา