คู่มือโอลิมปิกคอมพิวเตอร์

Computer Olympiad Guide for Thai High School Students

← กลับสู่หน้าหลัก (Back to Home)

Big O Notation

ทำไมต้องวิเคราะห์ความเร็ว

ในการแข่งขัน โปรแกรมต้องตอบถูก และ ทำงานเสร็จภายในเวลาที่กำหนด (มักเป็น 1 วินาที) การออกแบบวิธีที่ถูกแต่ช้ามักง่าย ความท้าทายอยู่ที่การหาวิธีที่เร็วพอ

Time complexity คือการบอกว่าจำนวนคำสั่งที่โปรแกรมทำ โตขึ้นอย่างไร เมื่อขนาด input n โตขึ้น โดยเขียนด้วยสัญลักษณ์ O(\cdots) ทำให้รู้ว่าวิธีไหนผ่านเวลาได้ ก่อน ลงมือเขียนโค้ด

Motivation problem

โค้ดสองชุดนี้ ชุดไหนเร็วกว่ากันเมื่อ n = 10^{5}

// แบบ A
for (int i = 1; i <= n; i++)
  for (int j = i + 1; j <= n; j++)
    work();

// แบบ B
for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j += i)
    work();

ทั้งคู่เป็น loop สองชั้น แต่จำนวนรอบต่างกันมาก

  • แบบ A: รอบในทำ n - i ครั้ง รวม \frac{n(n - 1)}{2} ครั้ง เป็น O\left( n^{2} \right)

  • แบบ B: รอบในทำประมาณ \frac{n}{i} ครั้ง รวม n\left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) \approx n\ln n เป็น O\left( n\log n \right)

n แบบ A แบบ B
10^{3} 499,500 8,053
10^{4} 49,995,000 103,643
10^{5} 4,999,950,000 1,266,714

บทเรียน: อย่านับแค่จำนวนชั้นของ loop ให้ดูว่าแต่ละชั้นวนกี่รอบจริง

กฎการคำนวณ

Loop

Loop ที่วน n รอบเป็น O(n) และ loop ซ้อน k ชั้นที่แต่ละชั้นวน n รอบเป็น O\left( n^{k} \right)

for (int i = 1; i <= n; i++)        // O(n)
  for (int j = 1; j <= n; j++)      // O(n) ต่อรอบนอก
    work();                         // รวม O(n^2)
ไม่สนค่าคงที่และพจน์ที่เล็กกว่า

Big O สนใจแค่ อันดับการเติบโต (order of magnitude) loop ที่วน 3n, n + 5 หรือ \frac{n}{2} รอบ เป็น O(n) ทั้งหมด และ n^{2} + 100n เป็น O\left( n^{2} \right) เพราะเมื่อ n ใหญ่ n^{2} ครอบงำทั้งหมด

หลาย phase ต่อกัน

ถ้าทำงานหลายช่วงต่อกัน complexity รวมคือของช่วงที่ช้าที่สุด (bottleneck) เช่น O(n) + O\left( n^{2} \right) + O(n) = O\left( n^{2} \right)

หลายตัวแปร

ถ้าขนาด input มีหลายค่า ให้เขียนด้วยหลายตัวแปร เช่น loop n รอบซ้อน loop m รอบเป็น O(nm) และ BFS บนกราฟเป็น O(n + m)

Loop ที่หารครึ่ง
for (int i = n; i > 0; i /= 2) work();  // O(log n)

n ถูกหารครึ่งได้ประมาณ \log_{2}n ครั้งก่อนเหลือ 0 เช่น \log_{2}10^{6} \approx 20 นี่คือที่มาของความเร็วของ binary search

Recursion

เวลาของ recursion = (จำนวนครั้งที่ฟังก์ชันถูกเรียก) \times (งานในแต่ละครั้ง)

void f(int n) {        // เรียก n ครั้ง ครั้งละ O(1): O(n)
  if (n == 1) return;
  f(n - 1);
}

void g(int n) {        // เรียก 1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1 ครั้ง: O(2^n)
  if (n == 1) return;
  g(n - 1);
  g(n - 1);
}

ดูภาพต้นไม้การเรียกฟังก์ชันได้ใน widget ของบท Recursion

Complexity classes ที่พบบ่อย

Complexity ชื่อ ตัวอย่าง
O(1) constant สูตรคณิตศาสตร์, เข้าถึง array
O\left( \log n \right) logarithmic binary search, set/map หนึ่งครั้ง
O\left( \sqrt{n} \right) square root หาตัวประกอบของ n
O(n) linear วนอ่าน array หนึ่งรอบ
O\left( n\log n \right) - sort, ทำ O\left( \log n \right) ไป n ครั้ง
O\left( n^{2} \right) quadratic พิจารณาทุกคู่
O\left( n^{3} \right) cubic loop สามชั้น, Floyd-Warshall
O\left( 2^{n} \right) exponential ลองทุก subset
O(n!) factorial ลองทุก permutation

ประเมินว่าผ่านเวลาหรือไม่

แทน n สูงสุดลงใน complexity แล้วเทียบกับประมาณ 10^{8} คำสั่งต่อวินาที เช่น n = 10^{5} กับ O\left( n^{2} \right) ได้ 10^{10} คำสั่ง ใช้ราว 100 วินาที ไม่ผ่านแน่นอน

ลองเปลี่ยนค่า n แล้วดูว่า complexity ไหนผ่านเวลา เปิด “ให้ฉันทายก่อน” แล้วคลิกแถวที่คิดว่าผ่าน ก่อนกดตรวจคำตอบ

ในทางกลับกัน ขนาด input ก็บอกใบ้วิธีแก้ได้: ถ้า n \leq 20 โจทย์อาจต้องการ O\left( 2^{n} \right) แต่ถ้า n \leq 2 \times 10^{5} ต้องคิดวิธี O\left( n\log n \right) หรือเร็วกว่า (ดูตารางในบทการเขียนโปรแกรมเชิงแข่งขัน)

ค่าคงที่ก็มีผล

Big O ไม่บอกค่าคงที่ วิธี O(n) ที่ทำ 50n คำสั่งอาจช้ากว่าวิธี O\left( n\log n \right) ที่เขียนเรียบง่าย ถ้า complexity อยู่ใกล้ขอบ (เช่น 10^{8} ถึง 10^{9}) ให้ระวังค่าคงที่ เช่น ใช้ map ซึ่งช้ากว่า array หลายเท่า

ต้นทุนที่ซ่อนอยู่

บางคำสั่งดูเหมือนบรรทัดเดียวแต่ไม่ใช่ O(1)

คำสั่ง เวลา
s = s + c (สร้าง string ใหม่) O\left( |s| \right) ใช้ s += c แทนซึ่งเฉลี่ย O(1)
v.erase(v.begin()) หรือ v.insert(v.begin(), x) O(n) เพราะต้องเลื่อนทุกตัว
ส่ง vector เข้าฟังก์ชันแบบ by value O(n) ทุกครั้งที่เรียก
set/map: insert, find, erase O\left( \log n \right)
sort O\left( n\log n \right)
v.push_back(x) เฉลี่ย O(1) (amortized ดูบท Dynamic Array)

Space complexity

วิเคราะห์หน่วยความจำได้ด้วย Big O เช่นกัน และโจทย์มักจำกัดหน่วยความจำ (เช่น 256 MB)

  • int ใช้ 4 byte ดังนั้น int a[10000000] (10^{7} ตัว) ใช้ 40 MB

  • long long ใช้ 8 byte

  • array 2 มิติขนาด 10^{4} \times 10^{4} ของ int ใช้ 400 MB เกินแน่นอน

ลองคิด

  1. for (int i = 1; i * i <= n; i++) วนกี่รอบ

  2. ถ้า n \leq 10^{6} วิธี O\left( n\sqrt{n} \right) ผ่านเวลา 1 วินาทีหรือไม่

  3. โค้ดที่ sort แล้ว binary search q ครั้งบน array ขนาด n มี complexity เท่าไร

เฉลย

  1. ประมาณ \sqrt{n} รอบ: O\left( \sqrt{n} \right)

  2. 10^{6} \times 10^{3} = 10^{9} คำสั่ง เสี่ยงเกินเวลามาก

  3. O\left( n\log n + q\log n \right)

โจทย์ฝึกฝน (Practice Problems)

ลองทำโจทย์เหล่านี้จาก CSES Problem Set เพื่อฝึกใช้ทักษะจากบทนี้ โดยเริ่มจากโจทย์ที่ง่ายที่สุดก่อน

โจทย์เพิ่มเติม: CSES Problem Set และ programming.in.th