Algorithm (อัลกอริทึม) คืออะไร?
Algorithm คือชุดคำสั่งที่มีจำนวนจำกัด ซึ่งหากปฏิบัติตามจะทำภารกิจเฉพาะเจาะจงสำเร็จ ไม่ผ속กับภาษาโปรแกรม ใช้ภาษาและสัญลักษณ์ใดก็ได้
เกณฑ์ของอัลกอริทึม
- Input (อินพุต): มีอินพุต 0 หรือมากกว่า ที่จัดหาจากภายนอก
- Output (เอาต์พุต): ให้ผลลัพธ์อย่างน้อย 1 อย่าง
- Definiteness (ความชัดเจน): ทุกคำสั่งชัดเจน ไม่คลุมเครือ
- Finiteness (ความจำกัด): จบสิ้นสุดภายในจำนวนขั้นตอนจำกัด สำหรับทุกกรณี
- Effectiveness (ความมีประสิทธิภาพ): ทุกคำสั่งต้องพื้นฐาน วัตถุประสงค์ชัดเจน
การวิเคราะห์อัลกอริทึม (Analysis of Algorithms)
การวิเคราะห์อัลกอริทึมเป็นส่วนสำคัญของทฤษฎีความซับซ้อนทางคำนวณ (Computational Complexity Theory) ให้การประมาณทฤษฎีสำหรับทรัพยากรที่อัลกอริทึมต้องการเพื่อแก้ปัญหาคำนวณใดๆ อัลกอริทึมส่วนใหญ่ถูกออกแบบให้ทำงานกับอินพุตความยาวเท่าไหร่ก็ได้ การวิเคราะห์คือการกำหนดปริมาณเวลาและพื้นที่ที่ต้องใช้
โดยทั่วไป ประสิทธิภาพหรือเวลาทำงานของอัลกอริทึมแสดงเป็นฟังก์ชันเชื่อมโยงความยาวอินพุตกับจำนวนขั้นตอน เรียกว่า Time Complexity หรือปริมาณหน่วยความจำ เรียกว่า Space Complexity
ความซับซ้อนของอัลกอริทึม (Complexities of an Algorithm)
ความซับซ้อนคำนวณเวลาและพื้นที่ที่อัลกอริทึมต้องการสำหรับอินพุตขนาด n แบ่งเป็น 2 ประเภทหลัก:
- Time Complexity (ความซับซ้อนด้านเวลา)
- Space Complexity (ความซับซ้อนด้านพื้นที่)
Time Complexity ของอัลกอริทึม
Time Complexity คือกระบวนการหาสูตรสำหรับเวลาทั้งหมดที่ใช้ในการทำงานของอัลกอริทึม การคำนวณนี้เป็นอิสระจากการนำไปใช้และภาษาโปรแกรม
Space Complexity ของอัลกอริทึม
Space Complexity คือกระบวนการหาสูตรเพื่อคาดการณ์ว่าต้องการพื้นที่หน่วยความจำเท่าไหร่สำหรับการทำงานสำเร็จ หน่วยความจำโดยทั่วไปหมายถึง Primary Memory
