กรณีดีที่สุด แย่ที่สุด และกรณีเฉลี่ย

ในการวิเคราะห์ประสิทธิภาพของของอัลกอริทึม กรณีดีที่สุด (best case) กรณีแย่ที่สุด (worst case) และ กรณีเฉลี่ย (average case)  คือ อัตราการใช้ทรัพยากรของอัลกอริทึมอย่างน้อยที่สุด มากที่สุด และ โดยเฉลี่ย ตามลำดับ โดยมักใช้สัญกรณ์โอใหญ่ (big O notation) ในการแสดงอัตราการใช้ทรัพยากรของอัลกอริทึมในแต่ละกรณี

ทรัพยากรที่อัลกอริทึมใช้ สามารถแบ่งได้เป็น 2 ด้าน คือ ด้านเวลา ใช้เวลาในการรัน (running time) หรือเรียกว่า ความซับซ้อนด้านเวลา (time complexity) เป็นหลัก ด้านที่สองคือ การใช้พื้นที่ความจำ (memory space) ของคอมพิวเตอร์ในการรันอัลกอริทึม หรือเรียกว่า ความซับซ้อนด้านพื้นที่ (space complexity)

กรณีที่ดีที่สุด คือ ฟังก์ชัน 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) 

 ควิกซอร์ต (Quicksort) ใช้ในการจัดเรียงลิสต์ที่มีสมาชิกอยู่ n ตัว โดยตั้งสมมติฐานว่าแต่ละตัวแตกต่างกัน (ไม่มีตัวไหนซ้ำกัน) โดยเป็นอัลกอริทึมที่ได้รับความนิยมใช้อย่างสูง อัลกอริทึมนี้มีประสิทธิภาพการเรียงในกรณีเฉลี่ยอยู่ที่ O(n log(n)) ทำให้อัลกอริทึมนี้เป็นอัลกอริทึมที่มีความเร็วสูงมากในการนำไปใช้งานจริง แต่ในกรณีที่แย่ที่สุด ควิกซอร์ตจำมีประสิทธิภาพการเรียงตกลงไปอยู่ที่ O(n2).

อ้างอิง 

ขั้นตอนวิธีการเรียงลำดับ