กรณีดีที่สุด แย่ที่สุด และกรณีเฉลี่ย
ในการวิเคราะห์ประสิทธิภาพของของอัลกอริทึม กรณีดีที่สุด (best case) กรณีแย่ที่สุด (worst case) และ กรณีเฉลี่ย (average case) คือ อัตราการใช้ทรัพยากรของอัลกอริทึมอย่างน้อยที่สุด มากที่สุด และ โดยเฉลี่ย ตามลำดับ โดยมักใช้สัญกรณ์โอใหญ่ (big O notation) ในการแสดงอัตราการใช้ทรัพยากรของอัลกอริทึมในแต่ละกรณี[1][2]
ทรัพยากรที่อัลกอริทึมใช้ สามารถแบ่งได้เป็น 2 ด้าน คือ ด้านเวลา ใช้เวลาในการรัน (running time) หรือเรียกว่า ความซับซ้อนด้านเวลา (time complexity) เป็นหลัก ด้านที่สองคือ การใช้พื้นที่ความจำ (memory space) ของคอมพิวเตอร์ในการรันอัลกอริทึม หรือเรียกว่า ความซับซ้อนด้านพื้นที่ (space complexity)[3]
กรณีที่ดีที่สุด คือ ฟังก์ชัน Big-O ในกรณีที่อัลกอริทึมได้รับอินพุต ในแบบที่รันได้รวดเร็วที่สุด ใช้ขั้นตอนในการรันต่ำที่สุดสำหรับการรันอินพุต n ชิ้น ยกตัวอย่างเช่น อัลกอริทึมเรียงแบบฟอง (bubble sort algorithm) กรณีที่ดีที่สุด คือ กรณีที่อินพุตที่เป็นตัวเลข เรียงจากน้อยไปมากเรียบร้อยแล้ว ทำให้เวลาอัลกอริทึมรันผ่านอินพุตแต่ละตัว จะใช้เวลาแค่ 1 หน่วยต่ออินพุตหนึ่งตัว มีฟังก์ชัน Big-O คือ O(n)
กรณีที่แย่ที่สุด คือ ฟังก์ชัน Big-O ในกรณีที่อัลกอริทึมได้รับอินพุต ในแบบที่ที่รันได้ช้าที่สุด อัลกอริทึมใช้ขั้นตอนในการรันมากที่สุด สำหรับการรันอินพุต n ชิ้น ยกตัวอย่างเช่น อัลกอริทึมเรียงแบบฟองกรณีที่แย่ที่สุด คือ กรณีที่อินพุตที่เป็นตัวเลข เรียงจากมากไปน้อย ทำให้เวลาอัลกอริทึมรันผ่านอินพุตแต่ละตัวจะใช้เวลานาน (รันจากตัวแรกไปตัวสุดท้าย ใช้เวลา O(n) รวมกับวนลูปข้างใน ใช้เวลา O(n)) กรณีนี้มีฟังก์ชัน Big-O คือ O(n^2)
กรณีเฉลี่ย คือ ฟังก์ชัน Big-O ในกรณีที่อัลกอริทึมได้รับอินพุต ในแบบที่ที่รันแบบเฉลี่ย อัลกอริทึมใช้ขั้นตอนในการรันโดยเฉลี่ย สำหรับการรันอินพุต n ชิ้น ยกตัวอย่างเช่น อัลกอริทึมเรียงแบบฟองกรณีเฉลี่ย ใช้เวลา O(n^2)
ตัวอย่าง
[แก้]อัลกอริทึมเรียงลำดับ (Sorting algorithms)
[แก้]| อัลกอริทึม (Algorithm) | โครงสร้างข้อมูล (Data structure) | ความซับซ้อนทางเวลาในกรณีดีที่สุด | ความซับซ้อนทางเวลาในกรณีเฉลี่ย | ความซับซ้อนทางเวลาในกรณีแย่ที่สุด | ความซับซ้อนทางพื้นที่ในกรณีแย่ที่สุด |
|---|---|---|---|---|---|
| ควิกซอร์ต
(Quick sort) |
Array | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| เมิร์จซอร์ต
(Merge sort) |
Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| ฮีพซอร์ต
(Heap sort) |
Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| สมูทซอร์ต
(Smooth sort) |
Array | O(n) | O(n log(n)) | O(n log(n)) | O(1) |
| บับเบิลซอร์ต
(Bubble sort) |
Array | O(n) | O(n2) | O(n2) | O(1) |
| อินเซอร์ชั่นซอร์ต
(Insertion sort) |
Array | O(n) | O(n2) | O(n2) | O(1) |
| ซีเล็กชั่นซอร์ต
(Selection sort) |
Array | O(n2) | O(n2) | O(n2) | O(1) |
| โบโก้ซอร์ต
(Bogo sort) |
Array | O(n) | O(n n!) | O(∞) | O(1) |
- ควิกซอร์ต (Quicksort) ใช้ในการจัดเรียงลิสต์ที่มีสมาชิกอยู่ n ตัว โดยตั้งสมมติฐานว่าแต่ละตัวแตกต่างกัน (ไม่มีตัวไหนซ้ำกัน) โดยเป็นอัลกอริทึมที่ได้รับความนิยมใช้อย่างสูง อัลกอริทึมนี้มีประสิทธิภาพการเรียงในกรณีเฉลี่ยอยู่ที่ O(n log(n)) ทำให้อัลกอริทึมนี้เป็นอัลกอริทึมที่มีความเร็วสูงมากในการนำไปใช้งานจริง แต่ในกรณีที่แย่ที่สุด ควิกซอร์ตจำมีประสิทธิภาพการเรียงตกลงไปอยู่ที่ O(n2).
อ้างอิง
[แก้]- ↑ Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".In Best-case complexity, it gives the lower bound on the running time of the algorithm of any instances of input.
- ↑ Lovász László (2009). Algoritmusok Bonyolultsága (ความซับซ้อนของอัลกอริทึม). Eötvös Loránd University. ลิงก์: https://www.uni-miskolc.hu/~matha/Gacs_Lovasz.pdf เก็บถาวร 2021-12-30 ที่ เวย์แบ็กแมชชีน
- ↑ Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.