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

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

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

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

รู้จักกับ basic operation

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

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

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

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

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$ เรามาทบทวนกันหน่อยซิว่าเจ้าเครื่องหมายนี้มีคุณสมบัติอย่างไรบ้าง

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

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

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

$\sum_{i=n}^{m} ca_i$ = $c\sum_{i=n}^{m}a_i$

$\sum_{i=n}^{m} (a_i + b_i) = \sum_{i=n}^{m} a_i + \sum_{i=n}^{m} b_i$

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

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

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

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

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

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

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(n - 1)$ ครั้ง

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

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

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

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

ในกรณีของ average-case เราสามารถใช้หลักความน่าจะเป็นมาคำนวณได้ซึ่งจะได้ค่าที่แม่นยำกว่านี้ แต่เราขอละในการอธิบายไว้ครับ เพราะผลสุดท้ายก็ได้ออกมาเป็น $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.