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

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

อ้างอิงแก้ไข

  1. 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.
  2. Lovász László (2009). Algoritmusok Bonyolultsága (ความซับซ้อนของอัลกอริทึม). Eötvös Loránd University. ลิงก์: https://www.uni-miskolc.hu/~matha/Gacs_Lovasz.pdf
  3. Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.