สัญกรณ์ Big O — ภาษากลางของการวัดประสิทธิภาพ

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

แนวคิดหลัก

เหตุใดเราจึง นับจำนวนการดำเนินการ (operations) แทนการ จับเวลาเป็นวินาที?

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

Big O ไม่สนใจว่า “ตอนนี้เร็วแค่ไหน” แต่สนใจว่า “เมื่อข้อมูลโตขึ้น มันจะแย่ลงเร็วแค่ไหน”

เราจึงวัด อัตราการเติบโต (growth rate) ของจำนวนการดำเนินการเมื่อขนาดข้อมูล n มีค่าเข้าสู่อนันต์ (n → ∞) และมีกฎสองข้อที่ทำให้การวิเคราะห์ง่ายขึ้น:

• ตัดค่าคงที่ทิ้ง: 2n กลายเป็น O(n), 500 กลายเป็น O(1) เพราะค่าคงที่ไม่ส่งผลเมื่อ n ใหญ่มาก
• เก็บเฉพาะพจน์ที่โตเร็วที่สุด: n² + n + 100 กลายเป็น O(n²) เพราะเมื่อ n ใหญ่ พจน์ n² ครอบงำพจน์อื่นทั้งหมด

สิ่งที่เราได้คือ “รูปร่างของการเติบโต” ที่บริสุทธิ์ ไม่ขึ้นกับฮาร์ดแวร์หรือภาษาใด ๆ

นิยามอย่างเป็นทางการ: ทำไมการ “ตัดทิ้ง” จึงถูกต้องทางคณิตศาสตร์

นี่ไม่ใช่การมโนเอาเอง — มันมีนิยามที่แม่นยำรองรับ (จาก CLRS บทที่ ๓): เราจะพูดว่า f(n) = O(g(n)) ก็ต่อเมื่อมี ค่าคงที่บวก c และ จุดเริ่มต้น n₀ ที่ทำให้

f(n) ≤ c · g(n)   สำหรับทุก n ≥ n₀

พูดง่าย ๆ คือ “ตั้งแต่จุดหนึ่งเป็นต้นไป (n₀) f(n) จะไม่มีวันแซง g(n) ที่คูณด้วยค่าคงที่บางตัว (c) ได้เลย”

ลองพิสูจน์จริง: ให้ f(n) = 3n² + 5n + 2 เราอ้างว่า f(n) = O(n²)

สำหรับ n ≥ 1 เราจะได้ 5n ≤ 5n² และ 2 ≤ 2n² เสมอ ดังนั้น

f(n) = 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n²

เลือก c = 10 และ n₀ = 1 ก็จบ — เราพิสูจน์ได้อย่างเข้มงวดว่า f(n) = O(n²) โดยไม่ต้อง “เดา” เลย นี่คือเหตุผลที่การตัดพจน์เล็กและค่าคงที่ทิ้งไม่ใช่การลัด แต่เป็นผลลัพธ์ที่พิสูจน์ได้จากนิยาม

Big O (O) คือ ขอบเขตบน, Big Omega (Ω) คือ ขอบเขตล่าง, และ Big Theta (Θ) คือกรณีที่ทั้งสองขอบเขตชนกัน (ขอบเขตที่แน่น) ในบทเรียนนี้เราเน้น O เพราะคำถามที่ใช้บ่อยที่สุดในงานจริงคือ “แย่ที่สุดได้แค่ไหน” — แต่ถ้าเจอ Θ(n log n) ในตำรา ให้รู้ว่ามันแม่นยำกว่า เพราะบอกทั้งขอบบนและขอบล่าง

สวนสัตว์แห่งความซับซ้อน

ตารางนี้เรียงจากดีที่สุดไปแย่ที่สุด พร้อมสัญชาตญาณว่า “ถ้า n = 1,000,000 จะรู้สึกอย่างไร”

สัญกรณ์	ชื่อ	ตัวอย่างจริง	n = 1,000,000 รู้สึกเหมือน…
O(1)	คงที่	เข้าถึงสมาชิกอาเรย์ด้วยดัชนี arr[i]	กระพริบตาเดียว — ไม่ว่าข้อมูลใหญ่แค่ไหนก็เท่าเดิม
O(log n)	ลอการิทึม	ค้นหาแบบทวิภาค (binary search)	~๒๐ ก้าว — เหมือนเปิดพจนานุกรมหาคำ
O(n)	เชิงเส้น	วนหาค่ามากสุดในรายการ	~๑ ล้านก้าว — เร็วมากสำหรับคอมพิวเตอร์
O(n log n)	เชิงเส้น-ลอการิทึม	การจัดเรียงที่ดี (merge sort, Timsort)	~๒๐ ล้านก้าว — ยังไหวสบาย
O(n²)	กำลังสอง	เปรียบเทียบทุกคู่ (nested loop)	~๑ ล้านล้านก้าว — เริ่มอืดเป็นนาทีถึงชั่วโมง
O(n³)	กำลังสาม	ลูปซ้อนสามชั้น เช่น การคูณเมทริกซ์แบบไร้เดียงสา	~๑๐¹⁸ ก้าว — เกินกำลังคอมพิวเตอร์ยุคปัจจุบันแล้ว
O(2ⁿ)	เลขชี้กำลัง	ลองทุกสับเซ็ต, ฟีโบนักชีแบบเรียกซ้ำไร้แคช	จักรวาลดับก่อนคำนวณเสร็จ

กฎสามัญสำนึก: O(n²) เริ่มน่ากังวลเมื่อ n แตะหลักหมื่น และ O(2ⁿ) ใช้ได้จริงเฉพาะเมื่อ n เล็กกว่า ~๔๐ เท่านั้น

ลองไล่เส้นโค้งการเติบโตทั้งหมดพร้อมกันแบบอินเทอร์แอกทีฟ — สลับเปิด/ปิดแต่ละเส้นดูว่าใครแซงใครตรงไหน:

อยากรู้สึกว่า O(n²) หน้าตาเป็นอย่างไรตอนทำงานจริง ลองดูการเรียงฟองสบู่ (bubble sort) ด้านล่าง สังเกตว่าจำนวนการเปรียบเทียบโตแบบกำลังสองเมื่อแท่งข้อมูลมากขึ้น:

กรณีดีที่สุด กรณีเฉลี่ย กรณีแย่ที่สุด

ลองนึกถึงการหากุญแจในกระเป๋า บางวันมือแตะโดนชิ้นแรกที่หยิบเลย (โชคดี) บางวันต้องเทของทั้งกระเป๋าออกมาหา (โชคร้าย) — อัลกอริทึมเดียวกันก็มี “วันโชคดี” และ “วันโชคร้าย” ต่างกันได้ ขึ้นอยู่กับว่าข้อมูลนำเข้าจัดเรียงมาแบบไหน

ลองดู insertion sort (การเรียงลำดับแบบแทรก):

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:  # เลื่อนสมาชิกที่ใหญ่กว่าไปทางขวา
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

• กรณีดีที่สุด (best case): ข้อมูลเรียงแล้ว → เงื่อนไข arr[j] > key เป็นเท็จทันที ลูป while ไม่ทำงานเลยสักครั้ง → O(n)
• กรณีแย่ที่สุด (worst case): ข้อมูลเรียงย้อนกลับ (มากไปน้อย) → ทุกสมาชิกใหม่ต้องเลื่อนผ่านสมาชิกที่แทรกไปแล้วทั้งหมด → O(n²)
• กรณีเฉลี่ย (average case): ข้อมูลสุ่ม → แต่ละสมาชิกเลื่อนผ่านไปประมาณครึ่งหนึ่งของที่แทรกแล้ว → ยังคงเป็น O(n²) (ค่าคงที่เล็กกว่า worst case แต่อันดับเดียวกัน)

กรณี	เกิดขึ้นเมื่อ	Insertion Sort	Quicksort (เลือก pivot ตัวแรก)
ดีที่สุด (Best)	ข้อมูลเรียงแล้ว / pivot แบ่งข้อมูลพอดีครึ่ง	O(n)	O(n log n)
เฉลี่ย (Average)	ข้อมูลสุ่ม	O(n²)	O(n log n)
แย่ที่สุด (Worst)	ข้อมูลเรียงย้อนกลับ / ข้อมูลเรียงแล้วบวก pivot ตัวแรกที่แย่ที่สุด	O(n²)	O(n²)

เมื่อพูดว่า “อัลกอริทึมนี้คือ O(n log n)” โดยไม่ระบุกรณี ค่าเริ่มต้นที่นักวิทยาการคอมพิวเตอร์หมายถึงคือ กรณีแย่ที่สุด (worst case) เพราะเป็นการรับประกันขอบเขตบนที่ปลอดภัยที่สุด — quicksort ขึ้นชื่อว่าเร็ว แต่ถ้าข้อมูลนำเข้าเรียงมาแล้วและเลือก pivot ไม่ฉลาด มันแย่พอ ๆ กับ bubble sort เลย

ความซับซ้อนด้านหน่วยความจำ (Space Complexity)

ถ้าความซับซ้อนด้านเวลาบอกว่า “ใช้เวลานานแค่ไหน” ความซับซ้อนด้านหน่วยความจำ (space complexity) ก็บอกว่า “ต้องกางพื้นที่ทำงานกว้างแค่ไหนระหว่างทำงาน” งานบางอย่างใช้พื้นที่คงที่ตลอด งานบางอย่างต้องเก็บข้อมูลเพิ่มตามขนาดของ n

ตัวอย่าง — ผลรวมแบบวนลูป (iterative):

def sum_all(arr):
    total = 0            # ตัวแปรเดียว ไม่ว่า arr จะยาวแค่ไหน
    for x in arr:
        total += x
    return total

ใช้ตัวแปรเสริมแค่ total ตัวเดียว ไม่ว่า arr จะมีสมาชิกกี่ตัว → O(1) space

ตัวอย่าง — แฟกทอเรียลแบบเรียกซ้ำ (recursive):

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

ทุกครั้งที่ฟังก์ชันเรียกตัวเอง ระบบต้องเก็บ เฟรมการเรียก (call stack frame) ไว้รอผลลัพธ์ ความลึกของการเรียกเท่ากับ n → O(n) space แม้ฟังก์ชันจะไม่ได้สร้างตัวแปรใหญ่ ๆ เลยก็ตาม

ฟังก์ชัน	เวลา (Time)	หน่วยความจำเสริม (Space)
sum_all (วนลูป)	O(n)	O(1)
factorial (เรียกซ้ำ)	O(n)	O(n) — call stack
binary search (วนลูป)	O(log n)	O(1)
binary search (เรียกซ้ำ)	O(log n)	O(log n) — call stack
merge sort	O(n log n)	O(n) — อาเรย์ชั่วคราวสำหรับ merge

กฎง่าย ๆ: ถ้าโค้ดเรียกตัวเองซ้ำ (recursion) ให้นับ ความลึกของการเรียก (recursion depth) เป็นหน่วยความจำเสมอ ไม่ว่าแต่ละเฟรมจะใช้พื้นที่น้อยแค่ไหนก็ตาม — นี่คือกับดักที่มือใหม่มองข้ามบ่อยที่สุด

ต้นทุนตัดจ่าย (Amortized Analysis): ทำไม array แบบไดนามิกยังคง “รู้สึกเหมือน” O(1)

ลองนึกถึงการออมเงิน “เผื่อวันฝนตก” — ส่วนใหญ่คุณจ่ายน้อย ๆ ทุกวัน นาน ๆ ครั้งถึงจะมีค่าใช้จ่ายก้อนใหญ่โผล่มา แต่ถ้าเฉลี่ยตลอดทั้งปี ค่าใช้จ่ายต่อวันก็ยังคงต่ำและคาดเดาได้

list.append() ใน Python ก็เป็นแบบนั้น ปกติมันคือ O(1) แต่เบื้องหลังคือ list ถูกเก็บในอาเรย์ขนาดคงที่ (fixed-size array) เมื่ออาเรย์เต็ม Python ต้องจอง อาเรย์ใหม่ที่ใหญ่กว่า (มักเป็น ๒ เท่า) แล้ว คัดลอกสมาชิกทุกตัว ไปยังอาเรย์ใหม่ — ซึ่งเป็นงาน O(n) คำถามคือ: แล้ว .append() ยังนับว่าเป็น O(1) ได้จริงหรือ?

ลองไล่ต้นทุนของการ append ทีละครั้ง เมื่อความจุ (capacity) ขยายเป็น ๒ เท่าทุกครั้งที่เต็ม:

append ครั้งที่	ความจุก่อนหน้า	ต้องขยายไหม?	ต้นทุน (คัดลอก + แทรก)	ต้นทุนสะสม
๑	๐	ขยายเป็น ๑	0 + 1 = 1	1
๒	๑	ขยายเป็น ๒	1 + 1 = 2	3
๓	๒	ขยายเป็น ๔	2 + 1 = 3	6
๔	๔	ไม่ต้อง	1	7
๕	๔	ขยายเป็น ๘	4 + 1 = 5	12
๖–๘	๘	ไม่ต้อง	1 ต่อครั้ง	15
๙	๘	ขยายเป็น ๑๖	8 + 1 = 9	24

ต้นทุนเฉลี่ยต่อการ append หลัง ๙ ครั้ง = 24 / 9 ≈ 2.67 — เป็น ค่าคงที่ ไม่โตตาม n เลย

พิสูจน์แบบทั่วไป (aggregate method): ผลรวมของต้นทุนการคัดลอกทั้งหมดคือ 1 + 2 + 4 + ... + n < 2n (อนุกรมเรขาคณิต) บวกกับต้นทุนแทรก n ครั้ง รวมแล้วไม่เกิน 3n ตลอดการ append ทั้งหมด n ครั้ง หารเฉลี่ยต่อครั้งจึงได้ค่าคงที่ → O(1) amortized

“ตัดจ่าย (amortized)” ไม่ได้แปลว่า “ทุกครั้งเร็ว” — บางครั้งการ append ครั้งเดียวยังคงเป็น O(n) จริง ๆ (ตอนขยายอาเรย์) แต่เมื่อเฉลี่ยตลอดทั้งชุดการดำเนินการ n ครั้ง ต้นทุนรวมไม่เกิน O(n) จึงเฉลี่ยออกมาเป็น O(1) ต่อครั้ง นี่คือเหตุผลที่ list.append() ใน Python และ ArrayList ใน Java ถูกเรียกว่า O(1) amortized ไม่ใช่ O(1) แบบเป๊ะ ๆ ทุกครั้ง

การอ่าน Big O จากโครงสร้างโค้ด

คุณไม่จำเป็นต้องท่องจำ — แค่มองโครงสร้างของโค้ดด้วยกฎห้าข้อนี้:

• ทำตามลำดับ = บวกกัน แล้วเก็บพจน์ที่ใหญ่ที่สุด
• วนซ้อนกัน = คูณกัน
• ลดขนาดปัญหาลงครึ่งหนึ่งทุกรอบ = log
• ตัวแปรควบคุมสองตัวที่ไม่เท่ากัน (n กับ m) ให้แยกกัน — อย่ารีบสรุปว่าลูปซ้อนกันต้องเป็น n² เสมอ
• การเรียกซ้ำ (recursion) ให้เขียนเป็นสมการทำซ้ำ (recurrence) แล้ววาดต้นไม้แห่งการเรียกซ้ำหรือใช้ Master Theorem

ตัวอย่างที่ ๑ — ลูปเดียว → O(n)

def find_max(nums):
    biggest = nums[0]
    for x in nums:        # วน n ครั้ง
        if x > biggest:
            biggest = x
    return biggest

ลูปเดียววนตามจำนวนข้อมูล → O(n)

ตัวอย่างที่ ๒ — ลูปซ้อนลูป → O(n²)

def has_duplicate(nums):
    for i in range(len(nums)):       # n ครั้ง
        for j in range(i + 1, len(nums)):  # ~n ครั้ง
            if nums[i] == nums[j]:
                return True
    return False

ลูปนอกคูณลูปใน = n × n → O(n²)

ตัวอย่างที่ ๓ — หารครึ่งทุกรอบ → O(log n)

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:                  # ขอบเขตหดครึ่งทุกรอบ
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

แต่ละรอบตัดข้อมูลทิ้งครึ่งหนึ่ง → O(log n) ลองไล่ทีละก้าวด้วยตัวเอง:

ตัวอย่างที่ ๔ — ทำตามลำดับ → บวกแล้วเก็บพจน์ใหญ่สุด

def process(nums):
    total = 0
    for x in nums:        # O(n)
        total += x
    nums.sort()           # O(n log n)
    return total, nums

O(n) + O(n log n) = O(n log n) เพราะเราเก็บเฉพาะพจน์ที่โตเร็วที่สุด

ตัวอย่างที่ ๕ — ตัวแปรสองตัวที่ไม่เท่ากัน → อย่ารวบเป็นตัวเดียว

def print_matrix(rows, cols):
    for r in range(rows):        # n ครั้ง (ตามจำนวนแถว)
        for c in range(cols):    # m ครั้ง (ตามจำนวนคอลัมน์)
            print(r, c)

ลูปนอกวนตามจำนวนแถว ลูปในวนตามจำนวนคอลัมน์ — สองค่านี้ไม่ใช่ตัวเดียวกัน จึงเป็น O(rows × cols) หรือเขียนเป็น O(n · m) ไม่ใช่ O(n²) (จะเป็น O(n²) ก็ต่อเมื่อ rows == cols เท่านั้น) ข้อผิดพลาดที่พบบ่อยคือรีบสรุปว่า “ลูปซ้อนกัน = n² เสมอ” ทั้งที่ต้องดูก่อนว่าตัวแปรควบคุมแต่ละลูปคืออะไรกันแน่

ตัวอย่างที่ ๖ — การเรียกซ้ำ (recursion) → เขียนเป็นสมการทำซ้ำ

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # T(n/2)
    right = merge_sort(arr[mid:])   # T(n/2)
    return merge(left, right)       # O(n) — รวมสองรายการที่เรียงแล้วด้วย two-pointer

เขียนต้นทุนเป็นสมการทำซ้ำ (recurrence): T(n) = 2T(n/2) + O(n) — แบ่งปัญหาเป็นสองส่วนครึ่งละหนึ่ง แล้วรวมผลด้วยต้นทุน O(n) เมื่อวาดเป็น ต้นไม้แห่งการเรียกซ้ำ (recursion tree) จะมีความลึก log n ชั้น แต่ละชั้นทำงานรวมกัน O(n) (เพราะข้อมูลถูกแบ่งแต่ไม่หาย) → รวมทั้งหมด O(n) × O(log n) = O(n log n)

ปัญหาจากโลกจริง

ลองนึกถึงฟีเจอร์ “ตรวจหารายชื่อผู้ใช้ที่ซ้ำกัน” ทีมพัฒนาเขียนโค้ดแบบนี้ แล้วทดสอบบนเครื่องตัวเองด้วยผู้ใช้ n = 100 คน — ทำงานเสร็จในพริบตา ผ่านการรีวิว ขึ้นโปรดักชัน

def find_duplicate_emails(users):
    duplicates = []
    for i in range(len(users)):
        for j in range(i + 1, len(users)):
            if users[i].email == users[j].email:
                duplicates.append(users[i].email)
    return duplicates

นี่คือ O(n²) เมื่อ n = 100 หมายถึง ~๕,๐๐๐ การเปรียบเทียบ — ว่องไว แต่เมื่อฐานผู้ใช้โตเป็น n = 10,000,000 มันกลายเป็น ~๕๐ ล้านล้าน การเปรียบเทียบ เซิร์ฟเวอร์ค้าง คำขอ timeout ผู้ใช้เห็นหน้าจอหมุนค้าง

วิธีแก้: ใช้ตารางแฮช (set) เพื่อจำอีเมลที่เคยเห็น ลดเหลือ O(n)

def find_duplicate_emails(users):
    seen = set()
    duplicates = []
    for u in users:           # วนรอบเดียว
        if u.email in seen:   # ตรวจสอบ O(1)
            duplicates.append(u.email)
        else:
            seen.add(u.email)
    return duplicates

บทเรียน: โค้ดที่ “ทำงานได้” บนข้อมูลทดสอบเล็ก ๆ อาจซ่อนระเบิดเวลา O(n²) ไว้ การอ่าน Big O คือเกราะป้องกันก่อนของจะพังในโปรดักชัน

แบบฝึกหัด

ตอบว่าโค้ดต่อไปนี้มีความซับซ้อน Big O เท่าใด

ข้อ ๑

def first_element(arr):
    return arr[0]

เฉลย

O(1) — เข้าถึงดัชนีเดียว ไม่ขึ้นกับขนาดของ arr

ข้อ ๒

def sum_all(arr):
    total = 0
    for x in arr:
        total += x
    return total

เฉลย

O(n) — ลูปเดียววนตามจำนวนสมาชิก

ข้อ ๓

def print_pairs(arr):
    for a in arr:
        for b in arr:
            print(a, b)

เฉลย

O(n²) — ลูปซ้อนลูป แต่ละลูปวน n ครั้ง → n × n

ข้อ ๔

def count_down(n):
    while n > 1:
        print(n)
        n = n // 2

เฉลย

O(log n) — n ถูกหารครึ่งทุกรอบ จำนวนรอบจึงเท่ากับ log ฐานสองของ n

ข้อ ๕

def mystery(arr):
    arr.sort()                 # ส่วน A
    for x in arr:              # ส่วน B
        for y in arr:
            if x == y:
                break

เฉลย

ส่วน A เป็น O(n log n) และส่วน B เป็น O(n²) ทำตามลำดับจึงบวกกัน: O(n log n) + O(n²) = O(n²) เพราะ n² โตเร็วกว่า

ข้อ ๖

def cartesian_print(a, b):
    for x in a:
        for y in b:
            print(x, y)

สมมติ a มีสมาชิก n ตัว และ b มีสมาชิก m ตัว โดย n ไม่เท่ากับ m ความซับซ้อนคือเท่าใด?

เฉลย

O(n · m) — ลูปนอกวนตาม a (n ครั้ง) ลูปในวนตาม b (m ครั้ง) ทั้งสองไม่ใช่ค่าเดียวกัน จึง ไม่ใช่ O(n²) เว้นแต่ len(a) == len(b)

ข้อ ๗

พิจารณา insertion_sort จากเนื้อหาด้านบน จงบอกความซับซ้อนเวลาในกรณีดีที่สุดและแย่ที่สุด เมื่อนำเข้าอาเรย์ [5, 4, 3, 2, 1] เทียบกับ [1, 2, 3, 4, 5]

เฉลย

[1, 2, 3, 4, 5] เรียงแล้ว → กรณีดีที่สุด O(n) (ลูป while ไม่ทำงานเลย)

[5, 4, 3, 2, 1] เรียงย้อนกลับสุด → กรณีแย่ที่สุด O(n²) (ทุกสมาชิกใหม่ต้องเลื่อนผ่านสมาชิกที่แทรกไปแล้วทั้งหมด)

ข้อ ๘

def sum_recursive(arr):
    if not arr:
        return 0
    return arr[0] + sum_recursive(arr[1:])

ฟังก์ชันนี้คืนผลรวมถูกต้อง แต่จงวิเคราะห์ ทั้งเวลาและหน่วยความจำ อย่างละเอียด (คำใบ้: arr[1:] สร้างลิสต์ใหม่ทุกครั้ง)

เฉลย

หน่วยความจำ: ความลึกของการเรียกซ้ำเท่ากับ n → O(n) space จาก call stack

เวลา: ดูเผิน ๆ เหมือน O(n) เพราะเรียก n ครั้ง แต่ arr[1:] เองก็เป็นการคัดลอกลิสต์ที่มีต้นทุน O(k) โดย k คือความยาวที่เหลือ รวมทั้งหมดคือ n + (n-1) + (n-2) + ... + 1 = O(n²) — นี่คือกับดักคลาสสิกที่โค้ด “ดูเหมือน” O(n) แต่จริง ๆ ซ่อน O(n²) ไว้จากการสไลซ์ลิสต์

ข้อ ๙

อธิบายว่าทำไม list.append() ใน Python จึงถูกเรียกว่า O(1) amortized ทั้งที่บางครั้งการขยายอาเรย์ภายในต้องคัดลอกสมาชิกทุกตัว (ซึ่งเป็น O(n)) หากมีการ append ทั้งหมด n ครั้งติดกัน ต้นทุนรวมและต้นทุนเฉลี่ยต่อครั้งคือเท่าใด?

เฉลย

การขยายอาเรย์ (double capacity) เกิดขึ้นที่ขนาด 1, 2, 4, 8, ..., n เท่านั้น (ไม่ใช่ทุกครั้ง) ต้นทุนรวมของการคัดลอกทั้งหมดคือ 1 + 2 + 4 + ... + n < 2n (อนุกรมเรขาคณิต) บวกกับต้นทุนแทรก n ครั้ง รวมแล้วไม่เกิน 3n ตลอดการ append ทั้งหมด n ครั้ง หารเฉลี่ยต่อครั้ง = ค่าคงที่ → O(1) amortized แม้บางครั้งครั้งเดียวจะเป็น O(n) จริงก็ตาม

ข้อ ๑๐

def binary_search_buggy(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid
        else:
            hi = mid
    return -1

โค้ดนี้มีบั๊กร้ายแรงซ่อนอยู่ หาให้เจอ แล้วบอกว่าเกิดอะไรขึ้นกับความซับซ้อนถ้าไม่แก้

เฉลย

บั๊กอยู่ที่บรรทัด lo = mid — ควรเป็น lo = mid + 1 เมื่อ arr[mid] < target ไม่เช่นนั้นเมื่อ hi - lo == 1 ค่า mid จะเท่ากับ lo เสมอ ทำให้ lo ไม่ขยับ วนซ้ำไม่รู้จบ (infinite loop)

ในทางทฤษฎี Big O สมมติว่าอัลกอริทึมต้อง จบการทำงาน (terminate) เสมอ — เวอร์ชันที่มีบั๊กนี้ไม่จบเลยในบางกรณี จึงพูดถึง Big O ไม่ได้ด้วยซ้ำ เมื่อแก้เป็น lo = mid + 1 แล้ว จะกลับมาเป็น O(log n) ตามปกติ นี่คือบทเรียนสำคัญ: Big O วัดอัลกอริทึมที่ ถูกต้อง เท่านั้น — ก่อนวิเคราะห์ความซับซ้อน ต้องอ่านให้แน่ใจก่อนว่าโค้ดทำงานถูกต้องด้วย

วิพากษ์โค้ดจาก AI

ลองสมมติว่าคุณพิมพ์พรอมต์นี้ให้ผู้ช่วย AI:

“เขียนฟังก์ชัน Python ที่รับรายการตัวเลขสองรายการ แล้วคืนค่ารายการของตัวเลขที่ปรากฏในทั้งสองรายการ”

แล้ว AI ตอบกลับมาด้วยโค้ดที่ ถูกต้อง ดังนี้

def common_elements(a, b):
    result = []
    for x in a:
        for y in b:
            if x == y and x not in result:
                result.append(x)
    return result

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

ลองหาจุดบกพร่องด้านประสิทธิภาพ แล้วเขียนพรอมต์ติดตามผล เช่น:

“โค้ดนี้เป็น O(n²) ช่วยเขียนใหม่ให้เป็น O(n) โดยใช้ set”

เฉลยและวิธีแก้

โค้ดเดิมเป็น O(n²) (แย่ยิ่งกว่านั้น เพราะ x not in result ก็เป็น O(n) ทำให้กรณีเลวร้ายแตะ O(n³)) เมื่อข้อมูลล้านตัวจะช้าจนใช้ไม่ได้

วิธีแก้คือใช้ set ซึ่งตรวจสอบสมาชิกได้ในเวลา O(1):

def common_elements(a, b):
    set_b = set(b)            # O(n)
    return list({x for x in a if x in set_b})  # O(n)

รวมเป็น O(n) เร็วกว่าเดิมมหาศาลเมื่อข้อมูลใหญ่

AI เก่งเรื่อง “เขียนโค้ดให้ถูก” แต่บ่อยครั้งเลือกวิธีที่ตรงไปตรงมาที่สุด ไม่ใช่วิธีที่ขยายขนาดได้ดีที่สุด — หน้าที่ตัดสินจึงยังเป็นของคุณ

🎮 เกมเดฟ: เลขคณิตงบเฟรม (frame budget) สำหรับตรวจชนกัน

เกมที่วิ่ง ๖๐ เฟรมต่อวินาที (FPS) มีเวลาให้ทำทุกอย่าง — รับ input, AI, ฟิสิกส์, ตรวจการชนกัน, เรนเดอร์ — เพียง ~๑๖.๖๗ มิลลิวินาทีต่อเฟรม ก่อนที่จอจะต้องอัปเดตใหม่อีกครั้ง Big O บอกได้ตรง ๆ ว่าต้นทุนต่อเฟรมของระบบหนึ่ง ๆ จะโตแค่ไหนเมื่อจำนวนเอนทิตี n เพิ่มขึ้น นั่นแปลว่าคุณทำนายได้ล่วงหน้า — ก่อนจะรันโปรไฟเลอร์ด้วยซ้ำ — ว่าโค้ด “ตรวจทุกคู่ของเอนทิตี” จะกินงบเฟรมทั้งหมดหรือไม่เมื่อด่านเริ่มแน่นขึ้น

ตัวอย่างที่ไล่จริง — ตรวจชนแบบทุกคู่ (naive) เทียบกับตารางกริดเชิงพื้นที่ (spatial grid):

def naive_collision_checks(entities):
    """O(n^2): เปรียบเทียบทุกคู่ของเอนทิตีหนึ่งครั้ง"""
    checks = 0
    n = len(entities)
    for i in range(n):
        for j in range(i + 1, n):
            checks += 1
            # ตรงนี้จะเรียก collides(entities[i], entities[j])
    return checks


def grid_collision_checks(entities, cell_size=64):
    """O(n) โดยเฉลี่ย: เปรียบเทียบเฉพาะเอนทิตีที่อยู่ในช่องกริดเดียวกัน"""
    buckets = {}
    for e in entities:
        key = (e["x"] // cell_size, e["y"] // cell_size)
        buckets.setdefault(key, []).append(e)

    checks = 0
    for bucket in buckets.values():        # แต่ละช่องมีเอนทิตีน้อยลงมาก
        m = len(bucket)
        checks += m * (m - 1) // 2          # เทียบเฉพาะคู่ *ภายในช่องเดียวกัน*
    return checks

เวอร์ชัน naive ต้องตรวจ n(n-1)/2 คู่เสมอ ไม่ว่าเอนทิตีจะอยู่ตรงไหน — เป็น O(n²) แบบคลาสสิก ส่วนเวอร์ชันกริดจะจัดกลุ่มเอนทิตีตามตำแหน่งก่อน (O(n)) แล้วเทียบเฉพาะเอนทิตีที่อยู่ในช่องเดียวกัน ถ้าเอนทิตีกระจายตัวสม่ำเสมอทั่วโลกเกม แต่ละช่องจะมีขนาด ค่อนข้างคงที่ แม้ n จะโตขึ้น ทำให้จำนวนการตรวจรวมเข้าใกล้ O(n) แทนที่จะเป็น O(n²)

ทีนี้ลองใส่ตัวเลขจริงให้เห็นว่า “งบพัง” คืออะไร สมมติระบบตรวจชนได้รับส่วนแบ่งของเฟรมประมาณ ๒ มิลลิวินาที และการตรวจแต่ละคู่ (เช่น เช็ก AABB หรือวงกลมทับกันแบบง่าย) ใช้เวลาประมาณ ๕๐ นาโนวินาที นั่นคืองบ ๒ ms / ๕๐ ns ≈ ๔๐,๐๐๐ การตรวจต่อเฟรม แก้สมการ n(n-1)/2 ≈ ๔๐,๐๐๐ ได้ n ≈ ๒๘๓ — เกินราว ๆ ๒๘๐ เอนทิตี ลูป O(n²) แบบ naive ตัวเดียวก็กินงบตรวจชนทั้งหมดไปเกินแล้ว ยังไม่ทันถึงฟิสิกส์หรือเรนเดอร์เลยด้วยซ้ำ ส่วนเวอร์ชันกริดที่ทำงานใกล้เคียง O(n) จะรองรับเอนทิตีได้เป็นหมื่นตัวในงบ ๒ มิลลิวินาทีเดียวกัน

รูป: จำนวนการเปรียบเทียบต่อเฟรม เทียบกับจำนวนเอนทิตี N เส้นโค้ง O(n²) แบบ naive ตัดเส้นงบ ๑๖ ms ที่ราว N ≈ 280 แล้วพุ่งต่อไม่หยุด ในขณะที่เส้นโค้ง spatial-grid O(n) แทบไม่ขยับในช่วงเดียวกัน

ลองเล่นจริง — วิดเจ็ตนี้รันทั้งสองวิธีที่จำนวนเอนทิตีเพิ่มขึ้นเรื่อย ๆ แล้วนับจำนวนการเปรียบเทียบแบบเรียลไทม์:

แบบฝึกหัด

เกม ๑

def update_particles(particles):
    for i in range(len(particles)):
        for j in range(len(particles)):
            if i != j:
                apply_repulsion(particles[i], particles[j])

ลูปนี้ในหนึ่งเฟรมมีความซับซ้อน Big O เท่าใด? ถ้าใช้งบ ~๔๐,๐๐๐ การตรวจจากด้านบน ที่ N ประมาณเท่าใดจะทำให้เฟรมเรตตกต่ำกว่า ๖๐ FPS?

เฉลย

เป็น O(n²) — แต่ละอนุภาควนตรวจอนุภาคอื่นทั้งหมด จึงเป็น n × (n-1) ≈ n² ครั้งต่อเฟรม (ข้อสังเกต: ที่นี่นับคู่แบบมีทิศทางทุกคู่ จึงเป็นสองเท่าของจำนวนคู่แบบไม่มีทิศทางในตัวอย่างด้านบน) แก้สมการ n² ≈ ๔๐,๐๐๐ ได้ n ≈ ๒๐๐ เกินราว ๆ ๒๐๐ อนุภาค ลูปนี้ตัวเดียวก็กินงบตรวจชนของเฟรมเกินแล้ว และเกมจะเริ่มตกต่ำกว่า ๖๐ FPS

เกม ๒

def move_entities(entities, dt):
    for e in entities:
        e["x"] += e["vx"] * dt
        e["y"] += e["vy"] * dt

โค้ดนี้มีความซับซ้อน Big O เท่าใด? มันเคยคุกคามงบ ๑๖ ms บ้างไหม แม้ที่ n = 100,000?

เฉลย

O(n) — อัปเดตค่าคงที่ต่อเอนทิตีหนึ่งครั้ง ไม่มีลูปซ้อน แม้ที่ n = 100,000 ก็เป็นแค่การคำนวณเลขง่าย ๆ ๑๐๐,๐๐๐ ครั้ง ซึ่งยังห่างไกลจากหลักล้านการดำเนินการที่งบ ๑๖ ms รองรับได้ที่ความเร็ว CPU ทั่วไป งานเชิงเส้นต่อเฟรมแทบไม่เคยทำให้งบพังด้วยตัวมันเอง — งานกำลังสองต่างหากที่เป็นตัวปัญหา

เกม ๓

ตารางกริดเชิงพื้นที่ในตัวอย่างด้านบนสมมติว่าเอนทิตีกระจายตัวสม่ำเสมอ จะเกิดอะไรขึ้นกับความซับซ้อนของมัน ถ้าเอนทิตีทั้งหมดกระจุกอยู่ในช่องกริดเดียว (เช่น ฝูงชนจำนวนมากยืนบนไทล์เดียวกัน)?

เฉลย

มันจะเสื่อมกลับไปเป็น O(n²) — ถ้าเอนทิตีทั้ง n ตัวตกลงในบักเก็ตเดียว grid_collision_checks จะคำนวณ m * (m-1) // 2 สำหรับบักเก็ตขนาด m = n ซึ่งก็คือจำนวนคู่แบบ naive เป๊ะ ๆ กริดจะช่วยได้ก็ต่อเมื่อเอนทิตีกระจายตัวอยู่ทั่วช่องต่าง ๆ จริง ๆ การกระจุกตัวแบบเลวร้ายที่สุดจะทำให้ประโยชน์ของกริดหายไปหมด นี่คือเหตุผลที่เอนจิ้นจริงเลือกขนาดช่องให้สัมพันธ์กับขนาด/การกระจายของเอนทิตี และบางครั้งต้องถอยไปใช้การแบ่งย่อยที่ละเอียดกว่า (quadtree) เมื่อช่องใดช่องหนึ่งรับภาระมากเกินไป

เกม ๔

sweep-and-prune broad phase จะเรียงเอนทิตีตามพิกัด x หนึ่งครั้งต่อเฟรม (O(n log n)) แล้วตรวจเฉพาะคู่ที่ช่วง x ทับกันตามลำดับที่เรียงแล้ว (ปกติเพิ่มอีกแค่ O(n) การตรวจ ถ้าเอนทิตีกระจายตัวพอสมควร) ความซับซ้อนรวมต่อเฟรมคือเท่าใด และทำไมวิธีนี้จึงมักปลอดภัยที่ ๖๐ FPS แม้ n จะมากถึงหลักพัน?

เฉลย

โดยรวมคือ O(n log n) — การเรียงลำดับครอบงำ เพราะ O(n log n) + O(n) เก็บเฉพาะพจน์ที่โตเร็วที่สุด เนื่องจาก log n โตช้ามาก (log₂(10,000) ≈ 13) งานรวมที่ n = 10,000 จึงอยู่ราว 130,000 การดำเนินการ — ยังอยู่ในงบระดับมิลลิวินาทีสบาย ๆ ต่างจาก O(n²) ที่ n เท่ากันซึ่งพุ่งเป็นล้านล้าน นี่คือเหตุผลที่ sweep-and-prune (และ spatial grid) เป็นคำตอบมาตรฐานเมื่อ “การตรวจชนกันในเกมช้าลง” ในเอนจิ้นจริง

โจทย์ท้าทาย

ท้าทาย ๑ — ตั้งงบให้เกมยิงกระสุนถล่ม (bullet hell)

คุณกำลังสร้างเกมยิงแนว bullet-hell ที่มีกระสุนสูงสุด ๒,๐๐๐ นัด และศัตรู ๕๐ ตัวพร้อมกันบนจอ การตรวจชน (กระสุนกับศัตรู, กระสุนกับผู้เล่น) ต้องเสร็จภายในงบ ๓ มิลลิวินาทีจากงบเฟรมทั้งหมด ๑๖ มิลลิวินาที ร่างแนวทางแก้ พร้อมอธิบายว่าทำไมการตรวจทุกคู่แบบ naive จึงล้มเหลว

แนวทาง

การตรวจทุกคู่แบบ naive คือ 2,050 × 2,049 / 2 ≈ ๒.๑ ล้าน คู่ต่อเฟรม แม้แต่ละคู่ใช้แค่ ๒๐ นาโนวินาที ก็ยังรวมเป็น ~๔๒ มิลลิวินาที มากกว่างบเฟรมทั้งหมดถึงสองเท่า ยิ่งไม่ต้องพูดถึงงบ ๓ มิลลิวินาที แนวทางที่ใช้ได้จริง: จัดกระสุนและศัตรูลงตารางกริดเชิงพื้นที่ที่ขนาดช่องใกล้เคียงรัศมีชนของกระสุน แล้วตรวจเฉพาะกระสุนกับศัตรูที่อยู่ในหรือติดกับช่องเดียวกัน — ข้ามการตรวจกระสุนกับกระสุนไปเลยเพราะกระสุนไม่ชนกันเอง เนื่องจากศัตรูมีน้อย (๕๐ ตัว) คุณอาจแค่วนศัตรู × กระสุนในช่องใกล้เคียงโดยไม่ต้องสร้างกริดเต็มรูปแบบสำหรับศัตรูก็ได้ กุญแจสำคัญคือตระหนักว่าคุณไม่จำเป็นต้องใช้ O((กระสุน+ศัตรู)²) — สิ่งที่ต้องการคือ O(กระสุน) การค้นหาเทียบกับกลุ่มศัตรูที่ถูกกรองด้วยพื้นที่ให้เล็กลง

ท้าทาย ๒ — โปรไฟเลอร์ไม่เคยโกหก

โปรไฟเลอร์ของคุณแสดงว่าขั้นตอนตรวจชนใช้เวลา ๑๒ มิลลิวินาทีที่ n = 800 เอนทิตี โดยใช้ลูป O(n²) แบบ naive ซึ่งกินงบ ๑๖ มิลลิวินาทีไปเกินแล้วด้วยตัวมันเอง คุณเปลี่ยนมาใช้ตารางกริดเชิงพื้นที่จากตัวอย่างด้านบน แล้วเวลาลดเหลือ ๐.๔ มิลลิวินาที ประมาณคร่าว ๆ ว่า n จะโตได้ถึงเท่าใด ก่อนที่เวอร์ชันกริดเองจะเสี่ยงเกินงบตรวจชน ๒ มิลลิวินาที — และยกตัวอย่างสถานการณ์ในเกมจริงหนึ่งอย่างที่จะทำลายสมมติฐาน O(n) ของกริด แม้ n จะไม่มากนัก

แนวทาง

ถ้ากริดรักษาขนาดบักเก็ตให้ค่อนข้างคงที่ จำนวนการตรวจจะโตใกล้เคียง O(n) ดังนั้นต้นทุนต่อเอนทิตีจะยังใกล้เคียงกับที่ ๘๐๐ เอนทิตี (๐.๔ ms / ๘๐๐ ≈ ๐.๐๐๐๕ ms/เอนทิตี) งบ ๒ มิลลิวินาทีจึงรองรับได้ราว ๒ / ๐.๐๐๐๕ ≈ ๔,๐๐๐ เอนทิตี — มากกว่าเพดานของเวอร์ชัน naive ที่ราว ๒๘๐ เอนทิตีจากตัวอย่างด้านบนเป็นสิบเท่า แต่นั่นตั้งอยู่บนสมมติฐานว่ากระจายตัวสม่ำเสมอ สถานการณ์เช่น “ห้องบอส” ที่เอนทิตีทั้งหมดมารุมเป้าหมายเดียว หรือกลไกฝูงสัตว์/แตกตื่นที่หน่วยต่าง ๆ เกาะกลุ่มกันแน่น จะดันเอนทิตีจำนวนมากเข้าไปในไม่กี่ช่อง และลากพฤติกรรมของกริดกลับไปเป็น O(n²) เฉพาะจุด — ตรงกับปัญหาการกระจุกตัวจากข้อเกม ๓ ด้านบน

เจาะลึกเพิ่มเติม

• MIT 6.006 Introduction to Algorithms — บันทึกการบรรยายเรื่องการวิเคราะห์ความซับซ้อน (MIT OpenCourseWare): https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
• Stanford CS161 Design and Analysis of Algorithms — เนื้อหาเรื่องสัญกรณ์เชิงเส้นกำกับ (asymptotic notation): https://stanford-cs161.github.io/winter2024/
• CLRS — Introduction to Algorithms, บทที่ ๓ “Growth of Functions” — ตำราอ้างอิงมาตรฐานเรื่องนิยามของ Big O, Ω และ Θ อย่างเข้มงวด ควรอ่านเพื่อเข้าใจการพิสูจน์ที่อยู่เบื้องหลังบทเรียนนี้
• Sedgewick & Wayne — Algorithms (ฉบับที่ 4) — มีบทวิเคราะห์ “resizing array” (ตัวเดียวกับที่เราไล่ตารางต้นทุนด้านบน) แบบละเอียดพร้อมโค้ด Java เทียบเคียงได้ตรง ๆ กับ dynamic array ใน Python
• Roughgarden — Algorithms Illuminated เล่ม ๑: The Basics — อธิบายสัญกรณ์เชิงเส้นกำกับด้วยภาษาที่เข้าถึงง่ายที่สุดในบรรดาตำราทั้งหมด เหมาะเป็นจุดเริ่มต้นก่อนอ่าน CLRS
• Big-O Cheat Sheet — ตารางสรุปความซับซ้อนของโครงสร้างข้อมูลและอัลกอริทึมยอดนิยม: https://www.bigocheatsheet.com/