Big-O — วัดว่าโค้ดเร็วหรือช้า

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

ไอเดียหลัก: นับว่าต้องทำงานกี่ครั้ง

สมมติมีลิสต์ยาว n ตัว เราถามว่า "โค้ดนี้ต้องแตะข้อมูลกี่ครั้งโดยประมาณ เมื่อเทียบกับ n" คำตอบนั้นแหละคือ Big-O เราสนแค่ "รูปทรงการโต" ไม่สนตัวเลขเป๊ะ ๆ (เช่น 2n กับ 5n ถือว่าโตแบบเดียวกัน = O(n))

nums = [4, 8, 15, 16, 23, 42]   # n = 6

# แตะข้อมูลครั้งเดียว — ไม่ขึ้นกับ n เลย  ->  O(1)
print(nums[0])

# วนครบทุกตัว 1 รอบ  ->  O(n)
for x in nums:
    print(x)

# วนซ้อนกัน 2 ชั้น ทุกคู่  ->  O(n^2)
for a in nums:
    for b in nums:
        print(a, b)

ระดับความเร็วที่เจอบ่อย (จากเร็วสุดไปช้าสุด)

ทำไมเราถึงตัดค่าคงที่ทิ้ง

ถ้าโค้ดวน 2 รอบเต็ม เราเขียน O(2n) แต่ Big-O สนแค่ "ทรงการโต" เมื่อ n ใหญ่มาก ๆ ค่าคงที่ 2 ไม่สำคัญ จึงเหลือ O(n) เหมือนกับที่ O(n^2 + n) เหลือแค่ O(n^2) เพราะพจน์ที่โตเร็วสุดครอบงำที่เหลือทั้งหมด

# ทั้งสองอันเป็น O(n) เหมือนกัน — ค่าคงที่ไม่นับ
for x in nums:      # รอบที่ 1
    print(x)
for x in nums:      # รอบที่ 2
    print(x)

# อันนี้ O(n^2) — พจน์ n^2 ครอบงำ n
for a in nums:          # n^2
    for b in nums:
        pass
for x in nums:          # + n  ->  ตัดทิ้ง เหลือ O(n^2)
    pass

Time vs Space

Big-O ใช้วัดได้ 2 อย่าง: (1) Time — ใช้เวลา/จำนวนครั้งเท่าไร (2) Space — ใช้หน่วยความจำเพิ่มเท่าไร เช่น ถ้าเราสร้างลิสต์ใหม่ขนาดเท่า input ก็ใช้ space O(n) แต่ถ้าแก้ไขในที่เดิมโดยไม่สร้างของใหม่ ก็ O(1) เวลาแก้โจทย์เรามักต้องแลกกันระหว่างสองอย่างนี้

เคล็ดลับอ่าน Big-O จากโค้ดเร็ว ๆ

• ไม่มี loop เลย / หยิบด้วย index / เช็คใน set,dict → O(1)
• loop เดียววน n ตัว → O(n)
• loop ซ้อน loop (ทั้งคู่วิ่งตาม n) → O(n^2)
• แต่ละก้าวตัดข้อมูลเหลือครึ่ง → O(log n)
• มี sort อยู่ในนั้น → อย่างน้อย O(n log n)
• ใช้ dict/set เพื่อแลก space มาลด time จาก O(n^2) เหลือ O(n) — เป็นเทคนิคที่เจอบ่อยมาก