Big-O notation คืออะไร?

Question

Accepted Answer

**Big-O** อธิบายว่าเวลาทำงานหรือหน่วยความจำของอัลกอริทึมเติบโตอย่างไรเมื่อขนาดอินพุต **n** เพิ่มขึ้น โดยจับพฤติกรรมแบบอะซิมโทติก *กรณีแย่ที่สุด* และละเลยค่าคงที่และพจน์ลำดับต่ำ

## แนวคิด

เราสนใจอัตราการเติบโต ไม่ใช่การนับขั้นตอนที่แน่นอน O(2n + 5) เป็นเพียง **O(n)** เพราะเมื่อ n เพิ่มขึ้นอย่างมาก ค่าคงที่และพจน์ที่เล็กกว่าจะไม่มีความสำคัญ

## คลาสทั่วไป

| Big-O | ชื่อ | ตัวอย่าง |
|-------|------|----------|
| O(1) | ค่าคงที่ | การค้นหาดัชนี array |
| O(log n) | ลอการิทึม | การค้นหาแบบไบนารี |
| O(n) | เชิงเส้น | การสแกนรายการ |
| O(n log n) | เชิงเส้น-ลอการิทึม | merge sort |
| O(n²) | กำลังสอง | ลูปซ้อนกัน |
| O(2ⁿ) | เลขชี้กำลัง | subsets แบบ naive |

## ตัวอย่าง

```python
def has_duplicate(nums):
    for i in range(len(nums)):        # outer loop: n
        for j in range(i + 1, len(nums)):  # inner loop: n
            if nums[i] == nums[j]:
                return True
    return False
# nested loops -> O(n^2) time, O(1) space
```

## อันตราย

Big-O ซ่อนค่าคงที่: อัลกอริทึม O(n) ที่มีค่าคงที่ขนาดใหญ่อาจแพ้ O(n log n) บนอินพุตเล็ก ๆ และติดตามความซับซ้อนของ **พื้นที่** ด้วย ไม่ใช่แค่เวลา

## ทำไมมันถึงสำคัญ

Big-O ให้คุณเปรียบเทียบอัลกอริทึมโดยไม่ต้องเรียกใช้หรือกังวลเกี่ยวกับฮาร์ดแวร์

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

นี่คือคำศัพท์ที่วิศวกรทุกคนใช้เพื่อให้เหตุผลเกี่ยวกับประสิทธิภาพ

O(1)	ค่าคงที่	การค้นหาดัชนี array
O(log n)	ลอการิทึม	การค้นหาแบบไบนารี
O(n)	เชิงเส้น	การสแกนรายการ
O(n log n)	เชิงเส้น-ลอการิทึม	merge sort
O(n²)	กำลังสอง	ลูปซ้อนกัน
O(2ⁿ)	เลขชี้กำลัง	subsets แบบ naive