Big O Notation คืออะไร วัดเองด้วยโค้ด JavaScript 4 ฟังก์ชัน

ลองนึกภาพว่าคุณเขียนฟังก์ชันหนึ่ง ทดสอบกับข้อมูล 1,000 ตัวแล้วเสร็จในพริบตา ทุกอย่างดูปกติดี จนวันหนึ่งข้อมูลโตเป็น 100,000 ตัว ฟังก์ชันเดิมกลับค้างไปเฉยๆ ทั้งที่ไม่ได้แก้โค้ดสักบรรทัด สิ่งที่อธิบายเรื่องนี้ได้คือ Big O และคำถามที่มักตามมาทันทีคือ "Big O คืออะไร ต้องเก่งคณิตไหมถึงจะเข้าใจ" ไม่ต้องเก่งคณิตก็เข้าใจได้ แค่ต้องนับเป็น ปัญหาคือบทความส่วนใหญ่อธิบาย Big O ด้วยกราฟเส้นโค้งกับสัญลักษณ์ ซึ่งอ่านจบแล้วก็ยังไม่รู้ว่ามันเกี่ยวอะไรกับโค้ดที่เราเขียนทุกวัน

วันนี้ Superdev Academy จะไม่ท่องนิยาม แต่จะพาไปวัดเอง เราเขียนฟังก์ชันสั้นๆ 4 ตัวด้วย JavaScript รันจริงที่ข้อมูล 1,000 / 10,000 / 100,000 ตัว แล้วนับว่าแต่ละตัวทำงานกี่รอบ ตัวเลขทั้งหมดในบทความนี้มาจากเครื่องของเราเอง คุณก๊อปโค้ดไปรันซ้ำได้ทุกบรรทัด

Big O ไม่ได้บอกว่าโค้ดเร็วแค่ไหน แต่บอกว่ามันช้าลงเร็วแค่ไหน

Big O Notation คือวิธีเขียนสั้นๆ ว่า เมื่อข้อมูลที่ส่งเข้าไป (เรียกว่า n) โตขึ้น จำนวนงานที่โค้ดต้องทำโตตามแบบไหน ถ้าข้อมูลเพิ่ม 10 เท่า งานเพิ่ม 10 เท่า เพิ่ม 100 เท่า หรือแทบไม่เพิ่มเลย เมื่อใช้ Big O บอกว่าเวลาทำงานโตตามข้อมูลแบบไหน เราเรียกเรื่องนี้ว่า Time Complexity (ถ้าวัดหน่วยความจำที่ใช้แทน จะเรียกว่า Space Complexity) บทความนี้เน้นฝั่งเวลาเป็นหลัก

พูดง่ายๆ มันไม่ได้ตอบว่า "ฟังก์ชันนี้ใช้กี่มิลลิวินาที" เพราะคำตอบนั้นขึ้นกับเครื่อง ภาษา และจังหวะที่รัน แต่มันตอบว่า "ถ้าวันหนึ่งข้อมูลโตจากหลักพันเป็นหลักแสน ฟังก์ชันนี้จะไหวไหม" ซึ่งเป็นคำถามที่สำคัญกว่าเยอะตอนระบบโตขึ้นจริง

ในบันทึกการสอนวิชา Introduction to Algorithms ของ MIT OpenCourseWare (6.006, Spring 2020) สรุปหลักของ Asymptotic Notation ไว้สั้นมาก คือให้ตัดตัวคูณคงที่ (Constant Factor) และพจน์ที่โตช้ากว่าทิ้ง เดี๋ยวเราจะเห็นกับตาว่าทำไมถึงทิ้งได้

4 ฟังก์ชันที่เราเอามาวัด

ทุกฟังก์ชันมีตัวนับ steps ที่เพิ่มขึ้นหนึ่งทุกครั้งที่ทำงานหลักหนึ่งรอบ การนับ step ดีกว่าการจับเวลาตรงที่มันได้ตัวเลขเดิมทุกครั้ง ไม่ว่าจะรันบนเครื่องไหน

// O(1): หยิบตัวแรกของ Array ทำงานรอบเดียวเสมอ
function getFirst(arr) {
  return arr[0];
}

// O(n): Linear Search ไล่หาทีละตัวจนเจอ
function linearSearch(arr, target) {
  let steps = 0;
  for (let i = 0; i < arr.length; i++) {
    steps++;
    if (arr[i] === target) return { index: i, steps };
  }
  return { index: -1, steps };
}

// O(n^2): เช็คว่ามีค่าซ้ำไหม ด้วย loop ซ้อน loop
function hasDuplicate(arr) {
  let steps = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      steps++;
      if (arr[i] === arr[j]) return { dup: true, steps };
    }
  }
  return { dup: false, steps };
}

// O(log n): Binary Search ใช้ได้กับ Array ที่เรียงแล้ว ตัดครึ่งทุกรอบ
function binarySearch(arr, target) {
  let steps = 0, lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    steps++;
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return { index: mid, steps };
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return { index: -1, steps };
}

ข้อมูลทดสอบคือ Array ของตัวเลข 0 ถึง n-1 เรียงกัน และเราตั้งใจเลือกกรณีที่แย่ที่สุด (Worst Case) ให้ทุกตัว คือค้นหาค่าที่ไม่มีอยู่ใน Array (เราใช้ค่า n ซึ่งมากกว่าทุกตัวใน Array) และเช็คค่าซ้ำใน Array ที่ไม่มีค่าซ้ำเลย ฟังก์ชันจึงต้องทำงานจนสุดทาง ถ้าอยากดูวิธีเขียน Linear Search กับ Binary Search แบบละเอียดทั้งฝั่ง JavaScript และ Go อ่านต่อได้ที่ JS2GO EP.36 การทำ Searching Algorithms ใน Go และ JavaScript

ผลที่วัดได้จริง: นับ step และจับเวลา

รันบน Apple M1 ด้วย Node.js v26.7.0 จำนวน step คือตัวเลขที่แน่นอน ส่วนเวลาคือค่าจากการรัน 2 รอบบนเครื่องเรา เครื่องของคุณจะได้ตัวเลขไม่เท่านี้ แต่สัดส่วนจะออกมาหน้าตาคล้ายกัน

เวลาที่จับได้บนเครื่องเรา: Linear Search ที่ n = 100,000 ใช้ประมาณ 0.06 ms ส่วน O(1) กับ O(log n) เร็วเกินกว่าจะจับเวลาได้แม่นในทุกขนาด ตัวที่เห็นชัดคือ hasDuplicate ซึ่งใช้ราว 0.3-1 ms ที่ n = 1,000 แล้วแต่รอบที่รัน, ประมาณ 49 ms ที่ n = 10,000 และ 13.2-13.9 วินาทีที่ n = 100,000

ลองอ่านตารางแนวตั้งดู ข้อมูลเพิ่ม 10 เท่าทุกแถว O(1) นิ่งอยู่ที่ 1 step, O(log n) เพิ่มแค่ 3-4 step, O(n) เพิ่ม 10 เท่าตาม และ O(n2) เพิ่มประมาณ 100 เท่า นี่คือสิ่งที่ Big O บอกล่วงหน้าได้โดยไม่ต้องรันจริงเลย

ที่ n = 100,000 Linear Search ทำ 100,000 steps แต่ loop ซ้อน loop ทำเกือบ 5,000 ล้าน steps กับข้อมูลชุดเดียวกัน

ทำไม 499,500 ถึงเขียนว่า O(n2) ไม่ใช่ตัวเลขเป๊ะๆ

ถ้านับละเอียด hasDuplicate เปรียบเทียบคู่ทั้งหมด n(n-1)/2 ครั้ง ที่ n = 1,000 ก็คือ 1,000 x 999 / 2 = 499,500 ตรงกับที่นับได้ กระจายสูตรออกมาจะได้ (1/2)n2 - (1/2)n

ตอน n ใหญ่ขึ้น ส่วน (1/2)n ตัวหลังแทบไม่มีผล ที่ n = 100,000 มันคือ 50,000 เทียบกับเกือบ 5,000 ล้าน ส่วน 1/2 ข้างหน้าก็ไม่เปลี่ยนรูปทรงของการโต เพราะไม่ว่าจะคูณ 1/2 หรือไม่ ข้อมูลเพิ่ม 10 เท่า งานก็ยังเพิ่มประมาณ 100 เท่าอยู่ดี Big O จึงเก็บไว้แค่ส่วนที่คุมการโต เหลือ O(n2)

หลักเดียวกันนี้ใช้กับโค้ดทุกแบบ ถ้าฟังก์ชันหนึ่งมี loop เดียววนสองรอบแยกกัน ได้ 2n ก็ยังเป็น O(n) ถ้ามี loop ซ้อน 2 ชั้นแล้วตามด้วย loop เดี่ยวอีกตัว ได้ n2 + n ก็เหลือ O(n2)

Big O มีกี่ประเภท

ตอบแบบตรงๆ ไม่มีจำนวนตายตัว Big O เขียนเป็นฟังก์ชันอะไรของ n ก็ได้ แต่ในงานจริงจะเจอซ้ำๆ อยู่ไม่กี่แบบ เรียงจากโตช้าไปโตเร็ว:

• O(1) — Constant: งานเท่าเดิมไม่ว่าข้อมูลจะเยอะแค่ไหน เช่น หยิบค่าจาก Array ด้วย index

• O(log n) — Logarithmic: ตัดปัญหาทีละครึ่ง เช่น Binary Search ที่ได้ 17 steps จากข้อมูล 100,000 ตัว

• O(n) — Linear: ต้องแตะข้อมูลทุกตัวหนึ่งครั้ง เช่น Linear Search

• O(n log n) — Log-linear: พบบ่อยในอัลกอริทึมเรียงข้อมูลที่ดี เช่น Merge Sort อ่านตัวอย่างโค้ดเรียงข้อมูลได้ที่ JS2GO EP.35 การทำ Sorting Algorithms

• O(n2) — Quadratic: loop ซ้อน loop อย่าง hasDuplicate

• O(2n) — Exponential: งานเพิ่มเป็นเท่าตัวทุกครั้งที่ n เพิ่มหนึ่ง

ตัวอย่าง O(2n) ที่เห็นง่ายที่สุดคือ Fibonacci แบบ Recursion ตรงๆ fib(n) = fib(n-1) + fib(n-2) เรานับจำนวนครั้งที่ฟังก์ชันถูกเรียกได้ 177 ครั้งที่ n = 10, 21,891 ครั้งที่ n = 20 และ 2,692,537 ครั้งที่ n = 30 ถ้าอยากเห็นว่าเปลี่ยนเป็น Iteration แล้วต่างกันยังไง ดูได้ที่ JS2GO EP.37 การใช้ Recursion และ Iteration

ตารางในบันทึกของ MIT ช่วยให้เห็นภาพชัดขึ้นอีก ถ้าเครื่องทำงานได้ 1 operation ต่อ 1 cycle ที่ 1 GHz และ n = 1,000 งานแบบ n2 จะใช้ประมาณ 1 ms ส่วนงานแบบ 2n ต้องใช้เวลาหลัก 10281 พันปี ตัวเลขนี้ไม่ได้พิมพ์ผิด มันคือเหตุผลที่โปรแกรมเมอร์กลัว Exponential มากที่สุด

Worst Case กับ Average Case ไม่ใช่เรื่องเดียวกัน

ตารางข้างบนเป็น Worst Case ทั้งหมด เพราะเราเลือกค่าที่ไม่มีอยู่จริงให้ค้นหา ถ้าค่าที่ค้นอยู่ตรงกลาง Linear Search จะเจอภายในประมาณ n/2 steps ซึ่งเร็วขึ้นครึ่งหนึ่ง แต่พอตัดตัวคูณคงที่ทิ้งก็ยังเป็น O(n) อยู่ดี

บางโครงสร้างข้อมูลมีสองค่าที่ต่างกันจริงๆ ตาราง TimeComplexity ของ Python Wiki ระบุว่าการเช็ค x in s บน list เป็น O(n) แต่บน set และ dict เป็น O(1) ในกรณีเฉลี่ย และ O(n) ในกรณีแย่ที่สุด เวลาอ่านเอกสารแบบนี้ ให้ดูเสมอว่าเขากำลังพูดถึงกรณีไหน

แล้ว Big O ที่ดีกว่าชนะเสมอไหม

ไม่เสมอ และนี่คือจุดที่หลายคนเข้าใจผิด เราลองเอา hasDuplicate แบบ loop ซ้อน (O(n2)) มาเทียบกับอีกวิธีที่ Big O ดีกว่า คือ new Set(arr).size !== arr.length ซึ่งใช้ Set ที่ MDN อธิบายว่าสเปกบังคับให้เข้าถึงข้อมูลได้เร็วกว่าเชิงเส้นในกรณีเฉลี่ย

• n = 5: loop ซ้อนใช้ประมาณ 13 ns, Set ใช้ประมาณ 61 ns

• n = 20: loop ซ้อนใช้ประมาณ 97 ns, Set ใช้ประมาณ 376 ns

• n = 1,000: loop ซ้อนใช้ประมาณ 0.29 ms, Set ใช้ประมาณ 0.021 ms

• n = 100,000: Set ใช้ประมาณ 4.7 ms ส่วน loop ซ้อนใช้ 13 วินาทีกว่าตามตารางข้างบน

ข้อมูลหลักสิบ วิธีที่ Big O แย่กว่ากลับเร็วกว่า เพราะการสร้าง Set มีต้นทุนคงที่ที่ Big O ตัดทิ้งไป แต่พอข้อมูลโตถึงหลักพัน Set ก็แซงขาด บทเรียนคือ Big O บอกทิศทางตอนข้อมูลโต ไม่ได้บอกว่าอะไรเร็วกว่าที่ขนาดหนึ่งๆ ถ้ารู้แน่ว่าข้อมูลเล็กตลอด โค้ดที่อ่านง่ายกว่ามักเป็นตัวเลือกที่ดีกว่า ถ้าไม่แน่ใจ ให้วัดแบบที่เราทำในบทความนี้

ลองหา Big O ของโค้ดตัวเองแบบง่ายๆ

ไม่ต้องพิสูจน์สูตร เริ่มจาก 3 ข้อนี้ก็พอ

1. หา loop ที่วนตามขนาดข้อมูล loop เดียวคือ n ซ้อนสองชั้นคือ n2 ถ้าแต่ละรอบตัดข้อมูลเหลือครึ่งคือ log n

2. ระวังของที่ซ่อน loop ไว้ข้างใน เช่น includes() หรือ indexOf() บน Array ที่เรียกใน loop ทำให้ O(n) กลายเป็น O(n2) โดยไม่รู้ตัว

3. ใส่ตัวนับ steps แล้วรันที่ n สองขนาดที่ต่างกัน 10 เท่า ถ้า step เพิ่ม 10 เท่าคือ O(n) เพิ่ม 100 เท่าคือ O(n2)

ถ้าอยากเห็นภาพการทำงานของอัลกอริทึมทีละขั้นควบคู่ไปด้วย ลองใช้เครื่องมือที่เราแนะนำไว้ใน การใช้ Visualizers เพื่อเข้าใจการทำงานของ Algorithm

สรุป: Big O คืออะไร และควรใช้มันแค่ไหน

Big O คือภาษาสั้นๆ ที่บอกว่างานของโค้ดโตแบบไหนเมื่อข้อมูลโตขึ้น จากที่เราวัดเอง ข้อมูลเพิ่มจาก 1,000 เป็น 100,000 ตัว Binary Search เพิ่มจาก 10 เป็น 17 steps ขณะที่ loop ซ้อน loop เพิ่มจาก 499,500 เป็นเกือบ 5,000 ล้าน steps ความต่างขนาดนี้คือเหตุผลที่ควรคิดเรื่อง Big O ก่อนข้อมูลจริงจะโต แต่ก็อย่าลืมอีกด้าน ที่ข้อมูลหลักสิบ โค้ดง่ายๆ ชนะได้จริง

สิ่งที่อยากฝากไว้คือ อย่าท่อง Big O เป็นตาราง ก๊อปฟังก์ชัน 4 ตัวข้างบนไปรันบนเครื่องคุณ เปลี่ยน n เอง แล้วดูตัวเลขขยับกับตา ความเข้าใจที่ได้จากการนับเองจะติดตัวนานกว่าการจำกราฟ

ติดตามบทความและเทคนิคสำหรับคนเริ่มต้นสายโปรแกรมเมอร์ได้ที่ช่องทางของเรา

Facebook: Superdev Academy Thailand (https://www.facebook.com/superdev.academy.th)

YouTube: Superdev Academy Channel (https://www.youtube.com/@SuperdevAcademy)

Instagram: @superdevacademy (https://www.instagram.com/superdevacademy/)

TikTok: @superdevacademy (https://www.tiktok.com/@superdevacademy?lang=th-TH)