ผลต่างระหว่างรุ่นของ "การวิเคราะห์ขั้นตอนวิธี"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล โรบอต เพิ่ม: fr:Analyse de la complexité des algorithmes |
Nullzerobot (คุย | ส่วนร่วม) ล เก็บกวาด |
||
บรรทัด 1:
{{ต้องการอ้างอิง}}
ในศาสตร์คอมพิวเตอร์
การวิเคราะห์ขั้นตอนวิธีเป็นส่วนที่มีความสำคัญของ[[ทฤษฎีความซับซ้อนในการคำนวณ]]ที่กว้างขึ้น ซึ่งเอื้ออำนวยสำหรับการประมาณการเชิงทฤษฎีสำหรับทรัพยากรที่จำเป็นต้องใช้โดยขั้นตอนวิธีใด ๆ สำหรับใช้ไขปัญหาที่ต้องการคำนวณ
การวิเคราะห์ขั้นตอนวิธีทางทฤษฎีเป็นวิธีการปกติที่ใช้ประเมินความซับซ้อนของมันเมื่อพิจารณาประสิทธิภาพของขั้นตอนวิธีกับชุดข้อมูลที่มีขนาดใหญ่มาก เช่น ประมาณฟังก์ชันความซับซ้อนสำหรับอินพุตขนาดใหญ่ใด ๆ [[สัญกรณ์โอใหญ่]] (Big O notation) [[สัญกรณ์โอเมก้า]] และ[[สัญกรณ์ธีต้า]] (theta notation) ถูกใช้เพื่อการนี้ด้วย ตัวอย่างเช่น การทำงานสำหรับ[[การค้นหาแบบทวิภาค]]เท่ากับจำนวนของขั้นตอนสัมพันธ์กับลอการิทึมของความยาวของรายการที่ต้องการค้นหา หรือ
การวัดประสิทธิภาพอย่างแม่นยำ บางครั้งสามารถคำนวณได้ แต่มันต้องการสมมติฐานที่แน่นอนเกี่ยวกับการดำเนินการเป็นพิเศษของขั้นตอนวิธี เรียกว่า[[โมเดลของการคำนวณ]] ซึ่งอาจนิยามในเทอมของ [[คอมพิวเตอร์นามธรรม]] เช่น [[เครื่องจักรทัวริง]] และ/หรือ โดยการสมมุติว่าการดำเนินการที่แน่นอนถูกกระทำในเวลาหนึ่งหน่วย ตัวอย่างเช่น การค้นหาอิลีเมนต์จากรายการที่จัดเรียงแล้ว (Sorted list) n อิลีเมนต์ ด้วยวิธีค้นหาแบบทวิภาค และเราสามารถรับประกันว่าการค้นหาอิลีเมนต์แต่ละครั้งทำในเวลาหนึ่งหน่วย ดังนั้นคำตอบที่ได้จะใช้เวลาในการค้นหาอย่างมากที่สุดเท่ากับ log<sub>2</sub> n + 1 หน่วยเวลา
| |||