สัญลักษณ์ Big O — อธิบายความซับซ้อนเชิงเวลาแบบเข้าใจง่าย

สัญลักษณ์ Big O ใช้บอกว่าเวลาในการทำงานหรือการใช้หน่วยความจำของอัลกอริทึมสามารถเพิ่มขึ้นได้เร็วแค่ไหนเมื่อขนาดข้อมูลนำเข้าเพิ่มขึ้น ถ้าคุณกำลังถามว่า “จะเกิดอะไรขึ้นเมื่อปัญหาใหญ่ขึ้นมาก?” Big O คือวิธีมาตรฐานในการตอบคำถามนี้

นั่นจึงเป็นเหตุผลที่คนพูดว่า linear search เป็น $O(n)$ และ binary search เป็น $O(\log n)$ เป้าหมายไม่ใช่การทำนายจำนวนมิลลิวินาทีที่แน่นอนบนเครื่องใดเครื่องหนึ่ง แต่คือการเปรียบเทียบรูปแบบการเติบโต

Big O หมายถึงอะไร

ถ้าอัลกอริทึมใช้เวลา $T(n)$ กับข้อมูลนำเข้าขนาด $n$ แล้ว

$$T(n) = O(f(n))$$

หมายความว่ามีค่าคงที่บางค่า $C > 0$ และ $n_0$ ที่ทำให้

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

นี่บอกว่า Big O เป็นข้อความเกี่ยวกับขอบเขตบนของการเติบโตสำหรับข้อมูลนำเข้าที่มีขนาดใหญ่พอ

พูดแบบง่าย ๆ คือ เมื่อ $n$ ใหญ่พอแล้ว เวลาในการทำงานจะไม่เพิ่มเร็วไปกว่าค่าคงที่คูณกับ $f(n)$

ทำไม Big O จึงมีประโยชน์

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

แนวโน้มนี้สำคัญมากที่สุดเมื่อขนาดข้อมูลเปลี่ยนไปมาก อัลกอริทึมที่ใช้ได้ดีสำหรับข้อมูล $100$ รายการ อาจใช้งานจริงไม่ได้เมื่อมีข้อมูล $10^6$ รายการ ถ้าอัตราการเติบโตของมันไม่ดี

ความซับซ้อนเชิงเวลาที่พบบ่อยแบบสรุป

• $O(1)$: ปริมาณงานยังคงมีขอบเขตจำกัดแม้ $n$ จะเพิ่มขึ้น
• $O(\log n)$: ปริมาณงานเพิ่มขึ้นช้า มักเกิดเมื่อขนาดปัญหาถูกลดลงซ้ำ ๆ
• $O(n)$: ปริมาณงานเพิ่มขึ้นประมาณเป็นสัดส่วนกับขนาดข้อมูลนำเข้า
• $O(n \log n)$: มากกว่าเชิงเส้นเล็กน้อย พบได้บ่อยในอัลกอริทึมเรียงลำดับที่มีประสิทธิภาพ
• $O(n^2)$: ปริมาณงานเพิ่มขึ้นเหมือนกำลังสองของขนาดข้อมูลนำเข้า มักเกิดจากลูปซ้อนที่ทำงานกับข้อมูลชุดเดียวกัน

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

ตัวอย่าง: ทำไม Linear Search จึงเป็น $O(n)$

สมมติว่าคุณไล่ดูรายการจากซ้ายไปขวาเพื่อหาค่าที่ต้องการ ในกรณีเลวร้ายที่สุด ค่านั้นอาจไม่มีอยู่เลยหรืออยู่ท้ายสุดของรายการ ดังนั้นคุณอาจต้องตรวจสอบทุกตัวหนึ่งครั้ง

ถ้ารายการมีทั้งหมด $n$ รายการ จำนวนครั้งที่ตรวจสอบจะมากที่สุดได้ไม่เกิน $n$ นั่นจึงเป็นเหตุผลที่เวลาในกรณีเลวร้ายที่สุดคือ

$$O(n)$$

ข้อสรุปสำคัญนั้นง่ายมาก: ถ้าขนาดของรายการเพิ่มเป็นสองเท่า จำนวนครั้งที่ต้องตรวจสอบในกรณีเลวร้ายที่สุดก็อาจเพิ่มขึ้นประมาณสองเท่าด้วย นี่คือรูปแบบที่ Big O พยายามอธิบาย

สิ่งที่ Big O ไม่ได้บอก

Big O ตั้งใจละเลยตัวคูณคงที่และพจน์อันดับต่ำกว่าเมื่อเปรียบเทียบการเติบโตสำหรับข้อมูลขนาดใหญ่

ตัวอย่างเช่น ถ้า

$$T(n) = 3n + 2$$

แล้ว $T(n)$ ก็ยังเป็น $O(n)$ อยู่ดี ค่าคงที่ $3$ และค่าเพิ่มอีก $2$ มีผลต่อเวลาจริงที่วัดได้ แต่ไม่ได้เปลี่ยนรูปแบบการเติบโตหลัก

แต่นั่นไม่ได้หมายความว่าค่าคงที่ไม่สำคัญในทางปฏิบัติ มันหมายถึงว่า Big O ตอบคำถามที่แคบกว่านั้น คือ ต้นทุนเพิ่มขึ้นอย่างไรเมื่อ $n$ มีค่ามาก

ข้อผิดพลาดที่พบบ่อยเกี่ยวกับ Big O

ข้อผิดพลาดที่ 1: คิดว่า Big O คือเวลาในการทำงานที่แน่นอน

$O(n)$ ไม่ได้แปลว่าเวลาในการทำงานเท่ากับ $n$ ขั้นตอนพอดี แต่มันหมายถึงการเติบโตถูกจำกัดจากด้านบนด้วยค่าคงที่คูณกับ $n$ เมื่อ $n$ ใหญ่พอ

ข้อผิดพลาดที่ 2: ลืมเงื่อนไขของ $n$ ที่มีค่ามาก

นิยามอย่างเป็นทางการต้องเป็นจริงเพียงสำหรับทุก $n \ge n_0$ เท่านั้น Big O พูดถึงพฤติกรรมเชิงเส้นกำกับเมื่อ $n$ มีค่ามาก ไม่ใช่ทุกกรณีของข้อมูลขนาดเล็กมาก

ข้อผิดพลาดที่ 3: คิดว่า Big O หมายถึงเวลาในการทำงานทั่วไปเสมอ

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

ข้อผิดพลาดที่ 4: เปรียบเทียบอัลกอริทึมด้วย Big O อย่างเดียว

Big O สำคัญมาก แต่การใช้หน่วยความจำ ต้นทุนในการพัฒนา และตัวคูณคงที่ ก็ยังมีผลมากในระบบจริง

คุณจะพบ Big O ได้ที่ไหน

Big O ปรากฏในวิทยาการคอมพิวเตอร์ คณิตศาสตร์ไม่ต่อเนื่อง และการวิเคราะห์ประสิทธิภาพ มันมีประโยชน์เป็นพิเศษเมื่อใช้เปรียบเทียบอัลกอริทึมสำหรับการค้นหา การเรียงลำดับ การท่องกราฟ และ dynamic programming

ในภาพกว้างกว่านั้น มันถูกใช้ทุกครั้งที่คุณสนใจว่ากระบวนการหนึ่งขยายตัวอย่างไร มากกว่าจะสนใจแค่ว่ามันทำงานอย่างไรที่ขนาดคงที่เพียงค่าเดียว

ลองทำตัวอย่างที่คล้ายกัน

ลองพิจารณาลูปซ้อนแบบง่ายที่วิ่งผ่านกริดขนาด $n \times n$ แล้วนับว่าการกระทำด้านในเกิดขึ้นกี่ครั้ง ถ้างานรวมทั้งหมดเติบโตเหมือน $n^2$ คุณก็จะได้ตัวอย่างที่ชัดเจนว่าทำไมลูปที่ทำซ้ำกับข้อมูลชุดเดิมจึงมักนำไปสู่พฤติกรรมแบบ $O(n^2)$