DAA - การวิเคราะห์อัลกอริทึม

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

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

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

ความจำเป็นในการวิเคราะห์

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

เมื่อพิจารณาอัลกอริทึมสำหรับปัญหาเฉพาะเราสามารถเริ่มพัฒนาการจดจำรูปแบบเพื่อให้สามารถแก้ไขปัญหาประเภทเดียวกันได้โดยใช้อัลกอริทึมนี้

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

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

• Worst-case - จำนวนก้าวสูงสุดที่ดำเนินการกับอินสแตนซ์ขนาดใดก็ได้ a.

• Best-case - จำนวนขั้นต่ำที่ดำเนินการกับอินสแตนซ์ขนาดใดก็ได้ a.

• Average case - จำนวนขั้นตอนโดยเฉลี่ยในอินสแตนซ์ขนาดใดก็ได้ a.

• Amortized - ลำดับของการดำเนินการที่ใช้กับการป้อนขนาด a เฉลี่ยตามช่วงเวลา

ในการแก้ปัญหาเราจำเป็นต้องพิจารณาเวลาและความซับซ้อนของพื้นที่เนื่องจากโปรแกรมอาจทำงานบนระบบที่หน่วยความจำมี จำกัด แต่มีพื้นที่เพียงพอหรืออาจกลับกันได้ ในบริบทนี้ถ้าเราเปรียบเทียบbubble sort และ merge sort. การจัดเรียงบับเบิ้ลไม่จำเป็นต้องใช้หน่วยความจำเพิ่มเติม แต่การเรียงลำดับการผสานต้องใช้พื้นที่เพิ่มเติม แม้ว่าความซับซ้อนของเวลาในการเรียงลำดับฟองจะสูงกว่าเมื่อเทียบกับการเรียงลำดับการผสาน แต่เราอาจต้องใช้การเรียงลำดับฟองหากโปรแกรมจำเป็นต้องทำงานในสภาพแวดล้อมที่หน่วยความจำมี จำกัด มาก