Big-O Notation — วัดประสิทธิภาพ

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

ตารางอันดับความเร็ว

สังเกตว่าเมื่อ n=1000 ความต่างระหว่าง O(n) (พันขั้น) กับ O(n²) (ล้านขั้น) มหาศาล นี่คือเหตุผลที่เราใส่ใจ Big-O

ดูตัวอย่างแต่ละระดับ

# O(1) — คงที่ ไม่ขึ้นกับขนาดลิสต์
def first(items):
    return items[0]          # ทำงานครั้งเดียวเสมอ

# O(n) — วนครั้งเดียว โตตามขนาด
def contains(items, target):
    for x in items:          # n รอบ
        if x == target:
            return True
    return False

# O(n²) — loop ซ้อน loop
def has_duplicate(items):
    for i in range(len(items)):       # n รอบ
        for j in range(i + 1, len(items)):  # อีก n รอบ
            if items[i] == items[j]:
                return True
    return False

วิธีอ่าน Big-O ของโค้ด

1. ไม่มี loop, แค่คำนวณ/เข้าถึง index/dict → O(1)
2. loop เดียววนทั้งข้อมูล → O(n)
3. loop ซ้อนสองชั้น (ทั้งคู่วนตามข้อมูล) → O(n²)
4. แบ่งครึ่งข้อมูลทุกรอบ (เช่น binary search) → O(log n)
5. เรียงลำดับ (sort) → O(n log n)

Space Complexity — หน่วยความจำก็นับ

Big-O ใช้วัดหน่วยความจำที่ใช้ด้วย ไม่ใช่แค่เวลา เช่นถ้าสร้างลิสต์ใหม่ขนาดเท่า input ก็ใช้ O(n) space ส่วนการใช้ตัวแปรไม่กี่ตัวคือ O(1) space

# O(1) space — ใช้ตัวแปรไม่กี่ตัว ไม่ว่า input ใหญ่แค่ไหน
def total(nums):
    s = 0
    for n in nums:
        s += n
    return s

# O(n) space — สร้างลิสต์ใหม่ขนาดเท่า input
def doubled(nums):
    return [n * 2 for n in nums]

สรุปหัวข้อนี้

• Big-O บอกว่างานโตตามขนาดข้อมูล n อย่างไร (ไม่ใช่วินาทีจริง)
• อันดับจากเร็วไปช้า: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• อ่านจากจำนวน loop ที่ซ้อนกัน: เดียว=O(n), สองชั้น=O(n²), แบ่งครึ่ง=O(log n)
• ตัดค่าคงที่และเก็บพจน์ที่โตเร็วสุด
• Space complexity วัดหน่วยความจำ: ตัวแปรไม่กี่ตัว=O(1), สร้างลิสต์ใหม่=O(n)