[Algorithm#2] วิเคราะห์อัลกอรึทึมด้วย Worst-Case, Best-Case และ Average-Case

Nuttavut Thongjor

เราทราบกันแล้วว่าการวิเคราะห์อัลกอริทึมนั้นเรานิยมมองที่ขนาดของจำนวนคำสั่งที่ใช้ในการประมวลผล กรณีที่อัลกอริทึมต้องทำงานคำสั่งทั้งสิ้น 2n2+42n ^ 2 + 4 คำสั่ง เราจะบอกว่า n2n ^ 2 เป็นจำนวนคำสั่งที่โดดเด่นสุดจนมีผลต่อประสิทธิภาพของอัลกอริทึม เราเรียกการวิเคราะห์ส่วนที่โดดเด่นนี้ว่า Big-O ด้วยเหตุนี้ 2n2+42n ^ 2 + 4 คำสั่ง จึงมี Big-O เป็น O(n2n ^ 2)

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

ก่อนที่เพื่อนๆจะเสพบทความนี้ ผมแนะนำเป็นอย่างยิ่งให้อ่าน สอนการวิเคราะห์ความซับซ้อนของอัลกอริทึมเบื้องต้น ก่อนครับ

รู้จักกับ basic operation

ในหนึ่งอัลกอริทึมประกอบด้วยคำสั่งหลายชุดหลายบรรทัดมาก หากให้เรามานับทุกคำสั่งก็ไม่ไหว นอกจากนี้ถ้าเราบอกว่าอัลกอริทึม A มีหนึ่งคำสั่ง และอัลกอริทึม B ก็ประกอบด้วยคำสั่งเดียวเช่นกัน แบบนี้เราสรุปไม่ได้นะครับว่าทั้งสองอัลกอริทึมจะมีประสิทธิภาพเท่ากัน

ถ้าคำสั่งของ A คือ 2 + 2 แต่คำสั่งของ B คือ 2 * 2 แม้จะประกอบด้วยคำสั่งเดียวเช่นกัน แต่โปรแกรม A มีแนวโน้มที่จะทำงานไวกว่าเพราะเครื่องหมายบวกนั้นเป็นการดำเนินการที่ไวกว่าการคูณ

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

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

Python
1# ฟังก์ชันสำหรับหาค่าสูงสุดจาก list
2def max(list):
3 maxValue = list[0]
4 currentIndex = 1
5
6 while currentIndex < len(list):
7 if list[currentIndex] > maxValue:
8 maxValue = list[currentIndex]
9 currentIndex += 1
10
11 return maxValue
12
13max([1, 4, 7, 9, 2]) # 9

จากตัวอย่างข้างต้นพบว่าในการวนลูปเราจะทำสองสิ่งเสมอนั่นคือ บรรทัดที่ 7 จะต้องตรวจสอบเงื่อนไข list[currentIndex] > maxValue เสมอ และบรรทัดที่ 9 จะทำการบวกเลขเสมอในทุกๆรอบของการวนลูป เราจึงกล่าวได้ว่าการวนลูปของอัลกอริทึมนี้มีการทำงาน 2 basic operations

เพื่อนๆอาจถามต่อไปว่าแล้วบรรทัดที่ 8 หละ? maxValue = list[currentIndex] มันก็อยู่ภายใต้ while เช่นกันไม่ใช่หรอ ทำไมเราไม่นับเป็น basic operation? เหตุผลเป็นเพราะคำสั่งนี้ไม่ได้ทำงานทุกครั้งที่วนลูปครับ แต่มันจะทำงานเมื่อเงื่อนไขในบรรทัดที่ 7 คือ if list[currentIndex] > maxValue เป็นจริงเท่านั้น เมื่อเป็นเช่นนี้มันจึงไม่ใช่คำสั่งหลักของเรา เป็นผลให้มันหมดโอกาสเป็น basic operation ครับ (เสียใจด้วยนะ)

สัญลักษณ์ซิกมาตัวใหญ่

ก่อนจะพูดถึงหัวข้อถัดไป เรามาทบทวนเรื่องผลบวกกันก่อนครับ ยังจำที่เคยเรียนสมัยมัธยมได้ไหมครับสัญลักษณ์ \sum เรามาทบทวนกันหน่อยซิว่าเจ้าเครื่องหมายนี้มีคุณสมบัติอย่างไรบ้าง

i=15x\sum_{i=1}^{5} x = 1 + 2 + 3 + 4 + 5

i=1n1\sum_{i=1}^{n} 1 = n

i=1ni\sum_{i=1}^{n} i = 1 + 2 + ... + n = n(n+1)2n( n + 1) \over 2

i=nmcai\sum_{i=n}^{m} ca_i = ci=nmaic\sum_{i=n}^{m}a_i

i=nm(ai+bi)=i=nmai+i=nmbi\sum_{i=n}^{m} (a_i + b_i) = \sum_{i=n}^{m} a_i + \sum_{i=n}^{m} b_i

จากสูตรข้างบน ถ้าผมบอกว่าต้องการบวกเลข 1 ถึง 10 ผมสามารถเขียนเป็นสัญลักษณ์ได้ว่า i=110xi\sum_{i=1}^{10} x_i นั่นคือบวกเลขตั้งแต่ 1 ถึง 10 โดย x เป็นตัวแปรที่เกิดขึ้นตรงกลางและเปลี่ยนค่าไปเรื่อยๆจาก 1 จนถึง 10 นั่นเอง

จากสูตรข้างต้นที่ว่า

i=1ni\sum_{i=1}^{n} i = 1 + 2 + ... + n = n(n+1)2n( n + 1) \over 2

ทำให้ผมทราบว่าการบวกเลขตั้งแต่ 1 ถึง 10 จะได้ค่าออกมาเป็น n(n+1)2n( n + 1) \over 2 หรือก็คือ 10(10+1)210( 10 + 1) \over 2 คือ 55

ประเมินประสิทธิภาพด้วย Worst-Case, Best-Case และ Average-Case

พิจารณาฟังก์ชันหาค่าสูงสุดต่อไปนี้

Python
1# ฟังก์ชันสำหรับหาค่าสูงสุดจาก list
2def max(list):
3 maxValue = list[0]
4 currentIndex = 1
5
6 while currentIndex < len(list):
7 if list[currentIndex] > maxValue:
8 maxValue = list[currentIndex]
9 currentIndex += 1
10
11 return maxValue
12
13# ตัวอย่างการเรียกใช้งาน
14max([1, 4, 7, 9, 2]) # ผลลัพธ์คือ 9

ก่อนที่เราจะเริ่มวิเคราะห์อัลกอริทึมให้มองหา basic operation ก่อนครับ ซึ่งเราได้หาไปแล้วจากหัวข้อก่อนหน้า basic operation ของลูป while มีค่าเป็นสอง แต่การทำงานของลูป while เราเริ่มตั้งแต่ 1 จนถึงความยาวของ list - 1 (currentIndex < len(list) เครื่องหมาย < แปลว่าไม่รวมตำแหน่งที่ len(list)) ถ้า list ของเรามีความยาวเป็น n เราจึงกล่าวได้ว่าเราต้องวนลูปทั้งหมด n - 1 ครั้ง (ถ้า n เป็น 3 เราจะวนลูปตั้งแต่ 1 และ 2 ไม่รวม 3) จึงสรุปได้ว่าสำหรับลูป while ของเราจะทำงานทั้งสิ้นเท่ากับ

basic operation ในลูป x จำนวนรอบ = 2(n1)2(n - 1) ครั้ง

ภายใต้ฟังก์ชัน max เรามีการประกาศตัวแปรในบรรทัดที่ 3 และ 4 ถือเป็นอีก 2 คำสั่ง จึงสรุปได้ว่าฟังก์ชัน max ของเราทำงานทั้งสิ้น 2(n1)+22(n - 1) + 2 หรือ 2n+12n + 1 มี Big-O เป็น O(n)O(n) นั่นเอง

การหาค่า max จากฟังก์ชันนี้พบว่า ไม่ว่าข้อมูลของ list จะมีหน้าตาเป็นอย่างไรฟังก์ชันของเราก็ยังต้องทำ 2n+12n + 1 คำสั่งอยู่ดี แม้ว่าค่าสูงสุดของเราจะอยู่ในตำแหน่งแรกของ list ซึ่งถือว่าเป็นกรณีที่ดีที่สุด (Best-Case) แต่โปรแกรมเราก็ยังต้องวนลูปต่อไปจนกว่าจะจบความยาว list เช่นเดียวกันต่อให้ค่าสูงสุดอยู่ปลายสุดของ list ซึ่งถือเป็นกรณีเลวร้ายที่สุด (Worst-Case) โปรแกรมเราก็ยังคงวนลูปจนจบเช่นกัน กรณีเช่นนี้กล่าวได้ว่าไม่มีข้อแตกต่างระหว่าง Best-Case และ Worst-Case

มาดูอีกตัวอย่างของการวิเคราะห์ Worst-Case, Best-Case และ Average-Case ครับ

Python
1def sequentialSearch(target, list):
2 # ตำแหน่งเริ่มต้นมีค่าเป็น 0
3 position = 0
4
5 while position < len(list):
6 # ถ้าสิ่งที่ต้องการหาอยู่ในตำแหน่งที่วนลูปอยู่พอดี
7 if target == list[position]:
8 # ให้คืนค่าตำแหน่งนั้นออกไป
9 return position
10 position += 1
11 # ถ้าหลุดมาถึงตรงนี้ได้ แสดงว่าหาไม่เจอ
12 # ให้คืนค่ากลับเป็น -1
13 return -1
14
15# ตัวอย่างการเรียกใช้
16print(sequentialSearch(3, [1, 2, 4, 3, 5])) # ผลลัพธ์เป็น 3

ตัวอย่างนี้คือฟังก์ชันหาค่าจาก list เช่นต้องการหาว่าเลข 3 อยู่ในตำแหน่งใดของ [1, 2, 4, 3, 5] หากหาพบให้คืนตำแหน่งที่เจอออกมา แต่ถ้าไม่เจออะไรในกอไผ่โปรดบอกฉันทีว่า -1

เช่นกันครับลูป while นี้มี 2 basic operations คือบรรทัดที่ 7 และ 10 สิ่งที่ต่างจากตัวอย่างก่อนหน้านี้คือฟังก์ชันนี้มี Worst-Case และ Best-Case ที่ไม่เหมือนกัน

  • กรณี Worst-Case: คือกรณีที่ค่าที่ต้องการหานั้นดันทะลึ่งไปอยู่ท้ายสุดของ list พบว่าเราต้องวนลูปไปจนสุด list จึงจะบอกได้ว่าค่าที่ต้องการหาอยู่ตำแหน่งใด กรณีนี้เราจึงกล่าวว่าฟังก์ชันของเรามี Worst-Case เป็น O(n)O(n) เพราะถ้า list ของเรามี n ไอเทม ก็ต้องวนลูป n ครั้ง
  • กรณี Best-Case: คือกรณีที่ค่าที่ต้องการหาอยู่ที่ช่องแรกของ list เลย โชคดีแบบนี้เราจึงมีประสิทธิภาพเป็น O(1)O(1) หรือพูดง่ายๆก็คือหาปุ๊บเจอปั๊บ
  • กรณี Average-Case: ความเป็นจริงช่างโชคร้ายครับ ยากที่ค่าที่ต้องการหาจะอยู่ช่องแรกสุดเลย และยากเช่นกันที่จะอยู่ช่องสุดท้าย เราจึงต้องเดาสุ่มว่ามันอาจอยู่ที่ไหนซักที่ใน list ของเราหรือเป็น average-case นั่นเอง การหาค่าเฉลี่ยที่ง่ายที่สุดก็เหมือนเราซื้อของมาจากตลาดหละครับ ถ้าเราซื้อของมาสามชิ้น เราจะบอกว่าเฉลี่ยแล้วของแต่ละชิ้นตกที่ราคาเท่าไหร่ เราต้องเอาราคาของทั้งหมดมาบวกกันแล้วหารด้วยจำนวนที่ซื้อมาคือ 3 ใช่ไหมครับ การหา average-case ก็เช่นกัน กรณีที่ค่าที่ต้องการหาอยู่ช่องแรกพอดีจะทำงานลูป 1 รอบ แต่ถ้าค่าที่ต้องการหาอยู่ในช่องที่สองจะวนลูป 2 รอบ ถ้าอยู่ในช่องที่ 3 ก็จะวนลูป 3 รอบ แต่ถ้า list เรามีของอยู่ n ชิ้น และของที่ต้องการหาอยู่ในช่องสุดท้ายพอดี เราต้องวนลูป n รอบ เราจึงกล่าวได้ว่าค่าเฉลี่ยการวนลูปของ list ที่มีของ n ชิ้นคือ (1 + 2 + 3 + ... + n) = i=1nxi\sum_{i=1}^{n} x_i = (n+1)2( n + 1) \over 2 หรือมี Big-O เป็น O(n)O(n) นั่นเอง

ในกรณีของ average-case เราสามารถใช้หลักความน่าจะเป็นมาคำนวณได้ซึ่งจะได้ค่าที่แม่นยำกว่านี้ แต่เราขอละในการอธิบายไว้ครับ เพราะผลสุดท้ายก็ได้ออกมาเป็น O(n)O(n) เช่นกัน

ทำไมเราจึงต้องวิเคราะห์หา Best-Case, Worst-Case

ต้องบอกก่อนเลยครับว่าการวิเคราะห์อัลกอริทึมนั้นเราให้ความสำคัญกับ worst-case และ average-case มากกว่า best-case มาก นั่นเพราะโดยเฉลี่ยผู้ใช้งานจะเผชิญกับประสิทธิภาพของอัลกอริทึมแบบเฉลี่ยหรือ average-case ไม่ใช่ best-case ในกรณีของ worst-case เป็นกรณีที่เลวร้ายจึงเป็นส่วนสำคัญที่เราต้องวิเคราะห์เป้นอย่างดี เพราะหากความเลวร้ายนั้นเป็นสิ่งที่ผู้ใช้งานรับไม่ได้ ลูกค้าอาจหายหนีไปใช้ผลิตภัณฑ์จากคู่แข่งได้เช่นกัน

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

บทความหน้าเราจะเริ่มการวิเคราะห์อัลกอริทึมไปกับกลยุทธิ์อย่างง่ายที่สุดคือ Brute Force โปรดติดตามฮะ

เอกสารอ้างอิง

Kenneth A. Lambert. Fundamentals of Python DATA STRUCTURES. Cengage Learning PTR, 2014.

Anany Levitin. Introduction to The Design and Analysis of Algorithms. Pearson Education, 2007.

สารบัญ

สารบัญ

  • รู้จักกับ basic operation
  • สัญลักษณ์ซิกมาตัวใหญ่
  • ประเมินประสิทธิภาพด้วย Worst-Case, Best-Case และ Average-Case
  • ทำไมเราจึงต้องวิเคราะห์หา Best-Case, Worst-Case
  • เอกสารอ้างอิง