บทนำสู่การวิเคราะห์อัลกอริทึม

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

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

โดยปกติ ประสิทธิภาพหรือเวลาทำงานของอัลกอริธึมจะระบุเป็นฟังก์ชันที่เกี่ยวข้องกับความยาวอินพุตกับจำนวนขั้นตอน เรียกว่า ความซับซ้อนของเวลา หรือปริมาตรของหน่วยความจำที่เรียกว่า ความซับซ้อนของพื้นที่ .

ในส่วนนี้ เราจะกล่าวถึง −

• อัลกอริทึมและความซับซ้อน
• การวิเคราะห์ด้วยอาการ
• สัญลักษณ์กำกับ
• การวิเคราะห์ค่าตัดจำหน่าย
• ความซับซ้อนของอวกาศ
• Pseudo Polynomial Type Algorithm และ PATS (Pseudo Polynomial Type ประมาณ Scheme)