[Algorithm#1] สอนการวิเคราะห์ความซับซ้อนของอัลกอริทึมเบื้องต้น

แต่ละปัญหาทางคอมพิวเตอร์มีทางออกได้หลายทาง การแก้ปัญหาด้วยวิธีแรกอาจใช้หน่วยความจำเยอะกว่าวิธีที่สองแต่ทำงานได้ไวกว่า วิธีที่สามอาจใช้หน่วยความจำน้อยสุดและทำงานได้ไวสุดแต่ผลลัพธ์ของการทำงานนั้นอาจไม่ถูกต้อง 100%

อัลกอริทึมคือชุดของคำสั่งที่มีลำดับการทำงานชัดเจนให้คอมพิวเตอร์เข้าใจได้ ในหนึ่งปัญหาที่เกิดขึ้นย่อมมีหลายอัลกอริทึมเพื่อแก้ปัญหา แต่วิธีการไหนหละดีที่สุด? เมื่อการเลือกอัลกอริทึมสำคัญเหมือนเลือกแฟน (จะหาใหม่ก็ยากเพราะดันมีลูกติดแล้วซะงั้น - -") ในบทความนี้จึงจะแนะนำการวัดความซับซ้อนของอัลกอริทึมให้เพื่อนๆรู้จักกันครับ

หมายเหตุ ตลอดทั้งชุดบทความนี้โปรแกรมที่จะแสดงใช้ภาษา Python 3 ทั้งสิ้น

ความซับซ้อนของอัลกอริทึม

เมื่ออัลกอริทึมนั้นเราคิดว่าใช้แก้ปัญหาได้แล้ว สิ่งที่เราควรตรวจสอบต่อไปได้แก่

• ความถูกต้องของอัลกอริทึม
• เวลาที่ใช้ในการทำงาน
• หน่วยความจำที่ใช้ไปจากการแก้ปัญหาด้วยอัลกอริทึมนี้

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

วัดเวลาที่ใช้ในการทำงานของอัลกอริทึม

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

1import time
2
3# ขนาดข้อมูล
4problemSize = 10000000
5print("%12s%16s" % ("Problem Size", "Seconds"))
6
7# ทำการวนลูป 5 ครั้งโดยแต่ละครั้งจะเพิ่มขนาด problemSize เป็นสองเท่า
8for loopCount in range(5):
9    startTime = time.time()
10    sum = 0
11    for i in range(problemSize):
12        sum += 1
13
14    # หาว่าใช้เวลาทำงานนานเท่าไร
15    elapsedTime = time.time() - startTime
16
17    print("%12d%16.3f" % (problemSize, elapsedTime))
18    problemSize *= 2

จากการทำงานของโปรแกรมดังกล่าวได้ผลลัพธ์ดังนี้

1Problem Size         Seconds
2    10000000           1.799
3    20000000           3.800
4    40000000           7.288
5    80000000          15.141
6   160000000          31.174

เพื่อนๆจะพบว่าขนาดของตัวเลขที่เพิ่มขึ้นสองเท่า จะทำให้ใช้เวลาทำงานนานขึ้นประมาณสองเท่าตัวเช่นกัน จากข้อมูลนี้เราจึงอนุมานได้ว่า ถ้าตัวเลขเราเปลี่ยนเป็น 320,000,000 เวลาที่ใช้ในการทำงานน่าจะเป็นสองเท่าของ 160,000,000 คือราวๆ 62 วินาที

การวัดความสามารถของอัลกอริทึมด้วยวิธีนี้ดูง่ายครับ แต่ก็มีข้อจำกัดอยู่ แหงหละถ้าข้อจำกัดไม่มีบทความคงสั้นเกินไปเป็นแน่ และต่อไปนี้หละครับคือข้อจำกัดของกระบวนการวัดดังกล่าว

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

วัดหน่วยความจำที่ใช้เพื่อการทำงานของอัลกอริทึม

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

นอกจากนี้ปริมาณการใช้หน่วยความจำและความเร็วมักเป็น trade-off ครับ คือได้อย่างเสียอย่าง ถ้าเอาเร็วเข้าว่ามักชอบบริโภคหน่วยความจำ แต่ถ้าประเภทกินน้อยมักทำงานช้าด้วย เป็นแบบนี้แล้วจะบอกได้ยังไงว่าใช้หน่วยความจำน้อยแล้วจะดีกว่า?

Complexity Analysis

Complexity Analysis หรือการวิเคราะห์ความซับซ้อนของอัลกอริทึม คือกระบวนการที่นำไปสู่การตัดสินใจว่าอัลกอริทึมไหนมีประสิทธิภาพมากกว่าโดยตัดเรื่องอื่นที่ไม่เกี่ยวข้องออกไป เช่น เวลาที่ใช้ไม่เท่ากันในแต่ละแพลตฟอร์ม (ภาษาโปรแกรมและระบบปฏิบัติการ) เป็นต้น

พิจารณาโปรแกรมต่อไปนี้

1p = 0
2
3for i in range(2, n + 1):
4    p = (p + i) * i

ถ้ากำหนดให้ n เป็นจำนวนเต็มบวกใดๆ จะได้ว่าในแต่ละรอบของ i ที่วนลูป จะทำการบวกและคูณอย่างละครั้ง รวมเป็นสองครั้ง โปรแกรมของเรามีการวนลูปทั้งหมดตั้งแต่ 2 จนถึง n หรือพูดได้ว่าวนลูปทั้งหมดเท่ากับ n - 1 รอบ เช่นถ้า n = 5 จะทำการวนลูปตั้งแต่ i เป็น 2, 3, 4 รวมทั้งสิ้น n - 1 คือ 5 - 1 ได้ 4 รอบ

เมื่อวนลูปทั้งหมด n - 1 รอบ ในแต่ละรอบมีการดำเนินการ 2 ครั้ง จึงได้ว่าโปรแกรมของเรามีการดำเนินการเพื่อบวกและคูณทั้งสิ้น 2(n - 1) คือ 2n - 2 รอบ

Big-O Notation

จากตัวอย่างที่ผ่านมามีการดำเนินการเพื่อทำงานด้วยอัลกอริทึมนี้ 2n - 2 รอบ มาลองคำนวนกันเล่นๆดีกว่าว่าถ้าค่า n ของเราเปลี่ยนไป จำนวนรอบจะเปลี่ยนไปอย่างไรบ้าง

เพื่อนๆจะสังเกตเห็นว่าขนาดของ n เป็นปัจจัยหลักที่ทำให้จำนวนรอบเพิ่มขึ้น ยิ่ง n มีค่ามากเท่าไหร่จำนวนยิ่งเพิ่มตามเช่นกัน ดังนั้น n ของเราจึงเป็น dominant term หรือส่วนที่โดดเด่นที่สุดจนเป็นตัวหลักที่เราต้องนำมาพิจารณาในการวิเคราะห์อัลกอริทึม กระบวนการที่เราใช้อธิบายประสิทธิภาพของอัลกอริทึมเมื่อเมื่อ n มีค่ามากภายใต้เงื่อนไขที่กำหนดแบบนี้เรียกว่า asymptotic analysis หรือแปลเป็นไทยเก๋ๆได้ว่าการวิเคราะห์เชิงกำกับ

ตัวอย่างที่เราวิเคราะห์กันว่า n คือ dominant term จนทำให้เราไม่สนใจค่าอื่นได้ เป็นหนึ่งใน asymptotic analysis ที่เรียกว่า big-O notation ย่อมาจาก on the order of

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

ลองมา Big-O ประเภทต่างๆของเรากันครับว่ามีรูปแบบไหนบ้าง โดยเรียงลำดับจากประสิทธิภาพดีสุดไปหาแย่สุดครับ

lg ในตารางข้างต้นหมายถึง log ฐานสอง และ n เป็นจำนวนเต็มไม่ติดลบ

ตลอดทั้งชุดบทความนี้เราจะใช้ Big-O เป็นหลักในการวิเคราะห์อัลกอริทึมของเรา เริ่มจากการค้นหาและการเรียงลำดับซึ่งจะกล่าวถึงในบทความถัดไป

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

สุพัชระ คงนวน. คณิตศาสตร์ดีสครีต. กรุงเทพมหานคร : สำนักพิมพ์มหาวิทยาลัยธรรมศาสตร์, 2557.

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