Data Structures & Algorithms
Fundamentals
บิ๊กโอ (Big-O notation): คู่มือฉบับเริ่มต้นแบบละเอียด
บทเรียนนี้สอนตั้งแต่ภาพรวมไปถึงการวิเคราะห์โค้ดทีละขั้น โดยเน้นให้เข้าใจว่าบิ๊กโอ (Big-O notation) สนใจแนวโน้มการเติบโตของเวลาและทรัพยากรเมื่ออินพุต (Input) โตขึ้น ไม่ใช่เวลาจริงเป็นวินาทีบนเครื่องใดเครื่องหนึ่ง
1. Big-O notation คืออะไร
บิ๊กโอ (Big-O notation) คือวิธีอธิบายว่าอัลกอริทึม (Algorithm) จะใช้เวลาทำงานหรือทรัพยากรเพิ่มขึ้นอย่างไร เมื่อขนาดอินพุต (Input Size: n) เพิ่มขึ้นเรื่อย ๆ
เราไม่ได้ถามว่าโค้ดนี้ใช้เวลา 0.01 วินาทีหรือ 0.02 วินาที แต่ถามว่าเมื่อข้อมูลโตจากหลักสิบเป็นหลักล้าน โค้ดจะโตแบบค่อย ๆ หรือพุ่งแรงแค่ไหน
2. ทำไมเราต้องวิเคราะห์ประสิทธิภาพของอัลกอริทึม
- เพื่อเลือกวิธีที่โตช้ากว่า: ตอนข้อมูลเล็ก วิธีต่างกันอาจดูไม่ชัด แต่เมื่อข้อมูลโต วิธีที่อัตราการเติบโต (Growth Rate) ดีกว่าจะช่วยประหยัดเวลามหาศาล
- เพื่อป้องกันปัญหาในระบบจริง: ระบบที่รับผู้ใช้จำนวนมาก ถ้าใช้อัลกอริทึมไม่เหมาะ อาจช้า ค้าง หรือกินทรัพยากรจนระบบล่มได้
3. Big-O บอกอะไร และไม่ได้บอกอะไร
- บอกอะไร: บอกแนวโน้มการเติบโตของจำนวนงาน เช่น O(1), O(log n), O(n), O(n^2) เมื่อ n ใหญ่ขึ้น
- ไม่ได้บอกอะไร: ไม่ได้บอกเวลาจริงแบบเป๊ะเป็นวินาที และไม่ได้สะท้อนความเร็วเครื่อง, ภาษาโปรแกรม หรือสภาพแวดล้อมรันไทม์ (Runtime)
4. ตัวอย่างจากชีวิตจริง
- หาเบอร์โทรในสมุดรายชื่อ: ถ้าไม่มีการเรียงชื่อ เราอาจต้องไล่ทีละชื่อ (เส้นตรง) ถ้าเรียงชื่อแล้วและเปิดกลางเล่มก่อน จะตัดครึ่งการค้นหาได้เรื่อย ๆ
- เช็กชื่อนักเรียนหน้าห้อง: ถ้าต้องเช็กทุกคน 1 รอบ งานจะโตตามจำนวนนักเรียนโดยตรง
- จับคู่เพื่อนทุกคนให้ทักกัน: ถ้ามี n คน และให้ทุกคนทักทุกคน จำนวนคู่จะโตเร็วมากแบบกำลังสอง
5. แนวคิดเรื่อง input size
อินพุตไซซ์ (Input Size: n) คือปริมาณข้อมูลที่เข้าอัลกอริทึม เช่น จำนวนสมาชิกในอาเรย์ ความยาวสตริง หรือจำนวนโหนดในกราฟ
เวลาเราบอกว่าอัลกอริทึมเป็น O(n) หมายถึง "ถ้า n โต งานก็โตตาม n" ไม่ได้ระบุค่าคงที่ตายตัวในแต่ละเครื่อง
6. แนวคิดเรื่องอัตราการเติบโต (growth rate)
อัตราการเติบโต (Growth Rate) คือภาพว่าเมื่อข้อมูลเพิ่ม งานเพิ่มเร็วแค่ไหน นี่คือหัวใจของบิ๊กโอ (Big-O notation)
ตัวอย่างเช่น O(log n) โตช้ากว่า O(n) และ O(n) โตช้ากว่า O(n^2) มากเมื่อ n มีขนาดใหญ่
7. ทำไมละค่าคงที่ได้
เพราะบิ๊กโอ (Big-O notation) สนใจแนวโน้มเมื่อ n ใหญ่มาก ไม่ได้สนใจจูนระดับ micro-optimization ตัวอย่างเช่น 3n กับ n เมื่อ n ใหญ่มาก ทั้งคู่ยังโตแบบเส้นตรง จึงจัดอยู่ในกลุ่ม O(n)
8. ทำไมสนใจพจน์ที่โตเร็วที่สุด
เมื่อ n ใหญ่มาก พจน์ที่โตเร็วสุดจะครองผลรวม ตัวอย่าง n^2 + n + 5 เมื่อ n โตมาก พจน์ n^2 มีผลหลักที่สุด จึงสรุปเป็น O(n^2)
9. ตัวอย่าง Big-O พื้นฐาน
- O(1): งานคงที่ เช่น เข้าถึงข้อมูลตำแหน่งเฉพาะ
- O(log n): งานโตช้า เพราะลดปัญหาครึ่งหนึ่งทุกรอบ
- O(n): งานโตตามจำนวนข้อมูลโดยตรง
- O(n log n): มักเจอในอัลกอริทึมแบ่งแล้วรวม เช่น เมิร์จซอร์ต (Merge Sort)
- O(n^2): โตเร็ว มักเกิดจากลูปซ้อนเทียบข้อมูลหลายคู่
- O(2^n): โตแบบเอ็กซ์โปเนนเชียล เร็วจนใช้งานยากเมื่อ n ใหญ่
10. ตัวอย่างโค้ด JavaScript ของแต่ละแบบ พร้อมวิเคราะห์ทีละขั้น
11. วิธีดู Big-O จาก loop เดี่ยว
ลูปวิ่งตามจำนวนสมาชิกทั้งหมด ถ้า n เพิ่มขึ้น จำนวนรอบเพิ่มตามนั้นตรง ๆ จึงเป็น O(n)
12. วิธีดู Big-O จาก nested loop
ลูปนอกประมาณ n รอบ และทุกรอบของลูปนอกมีลูปในประมาณ n รอบ งานรวมจึงเป็น n คูณ n = O(n^2)
13. วิธีดู Big-O จากการหารครึ่งข้อมูล
ทุกครั้งที่วนลูป ขนาดปัญหาลดเหลือครึ่งหนึ่ง จึงใช้จำนวนรอบประมาณ log n และสรุปเป็น O(log n)
14. ข้อผิดพลาดที่พบบ่อย
- คิดว่าบิ๊กโอ (Big-O notation) คือเวลาจริงเป็นวินาทีบนเครื่องของเรา
- คิดว่า O(1) แปลว่าเร็วเสมอทุกกรณี ทั้งที่ค่าคงที่จริงอาจสูง
- เห็นลูปสองชั้นแล้วสรุป O(n^2) ทันที ทั้งที่บางครั้งลูปในไม่ครบ n ทุกครั้ง
- ลืมแยกว่าเรากำลังวิเคราะห์เวลา (Time Complexity) หรือหน่วยความจำ (Space Complexity)
- สับสนระหว่างกรณีดีที่สุด (Best Case) กับกรณีแย่ที่สุด (Worst Case)
15. สรุปเปรียบเทียบ Big-O แต่ละแบบ
| รูปแบบ | ลักษณะการโต | ตัวอย่างงาน |
|---|---|---|
| O(1) | คงที่ | อ่านค่าตำแหน่งที่รู้ index |
| O(log n) | โตช้า | ค้นหาแบบหารครึ่ง |
| O(n) | โตตามข้อมูล | เดินครบหนึ่งรอบ |
| O(n log n) | กลาง ๆ สำหรับงานเรียงที่ดี | เมิร์จซอร์ต |
| O(n^2) | โตเร็ว | ลูปซ้อนสองชั้น |
| O(2^n) | พุ่งแรงมาก | แตกกิ่ง recursion แบบไม่เก็บผล |
16. สรุปท้ายบทแบบจำง่าย
บิ๊กโอ (Big-O notation) คือเครื่องมือเปรียบเทียบแนวโน้มการเติบโตของงาน เมื่ออินพุตใหญ่ขึ้น โดยไม่ยึดติดเวลาจริงบนเครื่องใดเครื่องหนึ่ง
หลักจำสั้น ๆ คือ ตัดค่าคงที่ เลือกพจน์ที่โตเร็วสุด และให้ความสำคัญกับ อัตราการเติบโต (Growth Rate) มากกว่าตัวเลขเล็ก ๆ ระยะสั้น
ถ้าต้องตัดสินใจระหว่างหลายวิธี ให้ถามเสมอว่าเมื่อข้อมูลโต 100 เท่า วิธีไหนยังรับไหวกว่า
17. แบบฝึกหัด 4 ข้อ พร้อมแนวเฉลย
ภาพประกอบการเติบโต
ภาพที่ 1: กราฟเปรียบเทียบการเติบโตของ O(1), O(log n), O(n), และ O(n^2) เมื่อขนาดอินพุตเพิ่มขึ้น จะเห็นว่า O(n^2) พุ่งขึ้นเร็วมากที่สุด
ภาพที่ 2: เมื่ออินพุตโตจาก 10 เป็น 1000 งานของ O(log n) เพิ่มน้อยมาก แต่ O(n^2) โตแบบกระโดด นี่คือเหตุผลที่บิ๊กโอ (Big-O notation) สำคัญกับงานข้อมูลขนาดใหญ่