Big O Notation คืออะไร?

ทำความรู้จักกับ Big O Notation กันเลย brother!

Big O Notation คือวิธีที่เราใช้วัดประสิทธิภาพของ algorithm — ไม่ใช่วัดเป็นวินาที แต่วัดว่า "ถ้า input เพิ่มขึ้น สิ่งที่ต้องใช้เพิ่มขึ้นยังไง?" และสิ่งที่ต้องใช้นั้นมีอยู่ 2 มิติ เสมอ:

• Time Complexity — งานที่ต้องทำเพิ่มขึ้นแค่ไหน?
• Space Complexity — หน่วยความจำที่ต้องใช้เพิ่มขึ้นแค่ไหน?

ลองนึกภาพแบบนี้: ถ้าข้อมูล 10 ชิ้น เร็ว 1 วิ พอข้อมูล 1 ล้านชิ้น จะใช้เวลาเท่าไหร่? และกิน memory เพิ่มขึ้นแค่ไหน? — นั่นแหละคือสิ่งที่ Big O บอก แล้ว Big O มีอะไรบ้างหล่ะ? มาดูกัน let go!

O(1) - Constant Time

ฺO(1) คือเวลาที่ไม่ขึ้นกับขนาดของ input เลย เช่น การเข้าถึง element ใน array โดยตรง หรือการเช็คว่า stack ว่างหรือเปล่า

ผมเปรียบเหมือนหยิบของชิ้นแรกออกจากกล่อง — กล่องใหญ่แค่ไหนก็ใช้เวลาเท่ากัน

โอเคเรามาดูตัวอย่างกัน:

function getFirstElement<T>(arr: T[]): T | undefined {
  return arr[0]; // Time: O(1), Space: O(1) — แค่นี้เลย ไม่สนว่า array มี 1 หรือ 1 ล้าน element
}

ไม่ว่า input จะใหญ่แค่ไหน ก็เร็วเท่าเดิม

คือจากตัวอย่างนี้ ไม่ว่า arr จะมีขนาดเท่าไหร่ เราก็แค่หยิบ element แรกออกมา — ใช้เวลา O(1) และกิน memory O(1) เพราะเราไม่ได้สร้างอะไรเพิ่มขึ้นตามขนาดของ input นั่นเอง! ง่ายๆ ไหมล่ะ?

O(n) - Linear Time

O(n) คือเวลาที่เพิ่มขึ้นตามขนาดของ input เช่น การวนลูปผ่าน array เพื่อหาค่าที่ต้องการ หรือการคัดลอกข้อมูลจากที่หนึ่งไปอีกที่หนึ่ง

ตัวอย่างง่ายๆ เลยคือนับนิ้วมือของเราเอง — ถ้ามี 5 นิ้ว ก็ต้องนับ 5 ครั้ง แต่ถ้ามี 10 นิ้ว ก็ต้องนับ 10 ครั้ง

มาดูตัวอย่างเป็นโค้ดที่เรารักกัน:

function findUser(users: User[], targetId: string): User | undefined {
  for (const user of users) { // วน loop ทุก element
    if (user.id === targetId) return user;
  }
  return undefined;
}

งานเพิ่มตาม input

ในตัวอย่างนี้ ถ้า users มี 10 คน เราต้องเช็ค 10 ครั้ง แต่ถ้ามี 1,000 คน เราต้องเช็ค 1,000 ครั้ง — นั่นแหละ O(n) my g! แต่จากในตัวอย่างนี้ Space Complexity เป็น O(1) เพราะเราไม่ได้สร้างอะไรเพิ่มขึ้นตามขนาดของ input ครับ

งั้นมาดูตัวอย่างที่มี Space Complexity เป็น O(n) กันบ้าง:

function copyArray<T>(arr: T[]): T[] {
  const copy: T[] = [];
  for (const item of arr) {
    copy.push(item); // เราสร้าง array ใหม่ที่มีขนาดเท่ากับ input — ดังนั้น Space Complexity เป็น O(n)
  }
  return copy;
}

งานเพิ่มตาม input ทั้งเวลาและหน่วยความจำ

ในตัวอย่างนี้ เราต้องสร้าง array ใหม่ที่มีขนาดเท่ากับ input เพื่อเก็บ copy ของ array — ดังนั้นเวลาที่ใช้เพิ่มขึ้นตามขนาดของ input (O(n)) และหน่วยความจำที่ใช้ก็เพิ่มขึ้นตามขนาดของ input ด้วย (O(n)) นั่นเอง!

O(n^2) - Quadratic Time

O(n^2) คือเวลาที่เพิ่มขึ้นแบบกำลังสองของขนาด input เช่น การใช้ nested loops เพื่อเปรียบเทียบทุกคู่ของข้อมูล หรือการเรียงลำดับข้อมูลแบบ bubble sort

ลองนึกภาพแบบนี้: ถ้าเรามี 3 คนในกลุ่ม และเราต้องจับคู่กันทั้งหมด จะมี 3 คู่ (A-B, A-C, B-C) แต่ถ้ามี 4 คน จะมี 6 คู่ (A-B, A-C, A-D, B-C, B-D, C-D) หรือถ้ามี 500คน ก็จะมี 124,750 คู่ — นั่นแหละ O(n^2)

well well well มาดูตัวอย่างโค้ดกัน:

function findDuplicates(arr: number[]): number[] {
  const duplicates: number[] = [];
 
  for (let i = 0; i < arr.length; i++) {         // O(n)
    for (let j = i + 1; j < arr.length; j++) {   // O(n) อีกรอบ → รวม O(n²)
      if (arr[i] === arr[j]) {
        duplicates.push(arr[i]);
      }
    }
  }
 
  return duplicates;
}

งานเพิ่มแบบกำลังสอง

ในตัวอย่างนี้ ถ้า arr มี 10 element เราต้องเช็ค 100 คู่ แต่ถ้ามี 1,000 element เราต้องเช็ค 1,000,000 คู่ — นั่นแหละ O(n^2) bro!

เราเห็นได้ชัดเลยว่า O(n^2) ไม่เหมาะกับข้อมูลขนาดใหญ่ เพราะมันจะทำให้เวลาที่ใช้เพิ่มขึ้นแบบทวีคูณ — ดังนั้นเราควรหลีกเลี่ยงการใช้ O(n^2) ถ้าไม่จำเป็นจริงๆ นะ!

แล้วเราจะทำยังไงถ้าเราต้องการหาคู่ที่ซ้ำกันใน array ที่มีขนาดใหญ่? เราสามารถใช้วิธีที่มีประสิทธิภาพมากขึ้น เช่น การใช้ hash set เพื่อเก็บค่าที่เราเจอแล้ว และเช็คว่าค่าปัจจุบันเคยเจอมาก่อนหรือเปล่า — ซึ่งจะทำให้เวลาที่ใช้ลดลงเป็น O(n) แทน O(n^2) นั่นเอง!

ตัวอย่างโค้ดที่ใช้ hash set:

function findDuplicates(arr: number[]): number[] {
  const seen = new Set<number>(); // สร้าง hash set เพื่อเก็บค่าที่เจอแล้ว 
  const duplicates: number[] = [];
  for (const num of arr) { // O(n) เพราะเราแค่เดินผ่าน array ครั้งเดียว
    if (seen.has(num)) {
      duplicates.push(num);
    } else {
      seen.add(num);
    }
  }
  return duplicates;
}

ใช้ hash set เพื่อหลีกเลี่ยง O(n^2)

O(log n) - Logarithmic Time

O(log n) คือเวลาที่เพิ่มขึ้นแบบลอการิทึมของขนาด input เช่น การใช้ binary search ใน array ที่เรียงลำดับแล้ว หรือการใช้ balanced tree ในการค้นหาข้อมูล

ตัวอย่างเช่น เวลาหาคำใน dictionary เราไม่ได้พลิกทีละหน้าจากต้น — เราเปิดกลางก่อน แล้วตัดสินใจว่าจะไปซ้ายหรือขวา ทำซ้ำแค่ ~20 ครั้ง ก็เจอจาก 1,000,000 หน้าได้

มาดูตัวอย่างโค้ดกัน:

function binarySearch(sortedArr: number[], target: number): number {
  let left = 0;
  let right = sortedArr.length - 1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) left = mid + 1;  // ตัดซีกซ้ายทิ้ง
    else right = mid - 1;                          // ตัดซีกขวาทิ้ง
  }
 
  return -1;
}

ตัดครึ่งทุกรอบ เร็วมาก

ในตัวอย่างนี้ ถ้า sortedArr มี 1,000,000 element เราแค่ต้องเช็คประมาณ 20 ครั้งเท่านั้น — นั่นแหละ O(log n) bro!

O(n log n) - Linearithmic Time

O(n log n) คือเวลาที่เพิ่มขึ้นแบบ n log n เช่น การเรียงลำดับข้อมูลด้วย merge sort หรือ quicksort ซึ่งเป็นอัลกอริทึมที่มีประสิทธิภาพสูงสำหรับการเรียงลำดับข้อมูลขนาดใหญ่

ถ้าจัดที่นั่งในห้องประชุมมี 1,000 คน แต่ละคนถือกระดาษที่มีชื่อตัวเอง ต้องเรียงตาม A-Z ถ้าจัดแบบ O(n²) คือ เดินตรวจทุกคู่ — เหนื่อยมาก อย่าหาทำกันนะ5555 ถ้าจัดแบบ O(n log n) คือ แบ่งเป็นกลุ่ม A-M กับ N-Z ก่อน แล้วแบ่งย่อยต่อ แล้วรวมกลับ — เร็วกว่าเยอะ

โอเค let's see โค้ดกัน:

// ทุก sort algorithm ที่ดีอยู่ที่ O(n log n) — นี่คือ lower bound ของการ sort
const sortedOrders = orders.sort((a, b) => a.amount - b.amount);
 
// ทุก built-in sort ใช้ O(n log n) ทั้งนั้น
[5,2,8,1].sort((a, b) => a - b);  // TimSort  → O(n log n)

"ราคาต่ำสุด" ของการ sort

O(2^n) - Exponential Time

O(2^n) คือเวลาที่เพิ่มขึ้นแบบทวีคูณของขนาด input เช่น การแก้ปัญหาแบบ brute-force ที่ต้องลองทุกความเป็นไปได้

ถ้าเรามี 3 สวิตช์ไฟ แต่ละสวิตช์มี 2 สถานะ (เปิด/ปิด) เราจะมี 2^3 = 8 วิธีในการตั้งค่าสวิตช์เหล่านั้น แต่ถ้ามี 10 สวิตช์ เราจะมี 2^10 = 1,024 วิธี — นั่นแหละ O(2^n)

มาดูตัวอย่างโค้ดกัน:

function fibonacci(n: number): number {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n) เพราะต้องคำนวณซ้ำๆ กันเยอะมาก
}

งานเพิ่มแบบทวีคูณ

จะเห็นได้ว่าในตัวอย่างนี้ ถ้า n = 30 เราต้องคำนวณประมาณ 2^30 ครั้ง ซึ่งเป็นจำนวนที่มหาศาล ซึ่งทำให้ O(2^n) ไม่เหมาะกับข้อมูลขนาดใหญ่เลยเพราะมันจะทำให้เวลาที่ใช้เพิ่มขึ้นแบบทวีคูณ 💀

แล้วเรามีวิธีแก้ปัญหาแบบนี้ไหม? แน่นอนว่าเราสามารถใช้เทคนิคที่เรียกว่า memoization หรือ dynamic programming เพื่อเก็บผลลัพธ์ของการคำนวณที่เคยทำไปแล้ว และนำมาใช้ใหม่เมื่อเจอ input เดิม

ตัวอย่างโค้ดที่ใช้ memoization:

function fibonacci(n: number, memo: Record<number, number> = {}): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n]; // เช็คว่าเคยคำนวณา n นี้แล้วหรือยัง
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); // เก็บผลลัพธ์ใน memo
  return memo[n];
}

ใช้ memoization เพื่อหลีกเลี่ยง O(2^n)

ในตัวอย่างนี้ เราใช้ object memo เพื่อเก็บผลลัพธ์ของการคำนวณ Fibonacci ที่เคยทำไปแล้ว เมื่อเราต้องคำนวณ Fibonacci ของ n ที่เคยคำนวณาแล้ว เราก็แค่ดึงผลลัพธ์จาก memo แทนที่จะคำนวณใหม่ทั้งหมด ซึ่งจะทำให้เวลาที่ใช้ลดลงเป็น O(n) แทน O(2^n) นั่นเอง!

Time vs Space — ของไม่มีฟรีในโลก

ที่ผ่านมาเราคุยกันแต่เรื่อง "เร็วแค่ไหน" แต่จริงๆ engineer ที่ดีต้องมองให้ครบทั้ง 2 มิติเสมอ และสิ่งที่ต้องรู้คือ space ที่เราวัดกันนี้ไม่ได้รวม input ด้วยนะ — เราวัดแค่ auxiliary space คือหน่วยความจำที่ algorithm สร้างขึ้นมาเพิ่มเองระหว่างทำงาน

แล้วทำไมต้องสนใจด้วย? เพราะใน real world เราแทบไม่เคยได้ทั้งสองอย่างพร้อมกันเลย — มันมักจะเป็น tradeoff เสมอ

จากตัวอย่างที่ผมเคยยกไปก่อนหน้านี้ findDuplicates

// version 1: O(n²) time — O(1) space
// ช้า แต่ไม่กิน memory เพิ่มเลย
function findDuplicates(arr: number[]): number[] {
  const duplicates: number[] = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) duplicates.push(arr[i]);
    }
  }
  return duplicates;
}
 

// version 2: O(n) time — O(n) space
// เร็วขึ้น แต่ต้องแลกด้วย memory ที่เพิ่มตาม input
function findDuplicates(arr: number[]): number[] {
  const seen = new Set<number>();
  const duplicates = new Set<number>();
  for (const num of arr) {
    if (seen.has(num)) duplicates.add(num);
    else seen.add(num);
  }
  return [...duplicates];
}

นี่แหละคือ time-space tradeoff ที่ engineer เจอในงานจริงบ่อยมาก — จะเอาเร็ว ก็ต้องจ่ายด้วย memory จะประหยัด memory ก็ต้องยอมช้าลง

ในทางปฏิบัติ ถ้า data ไม่ได้ใหญ่มากและ memory ไม่ใช่ constraint เราก็มักเลือก version ที่เร็วกว่า แต่ถ้า system มี memory จำกัด อันนี้ต้องคิดหนักกว่านั้นครับ

อีกอย่างที่หลายคนลืม — Call Stack ก็กิน memory นะ กลับมาดู fibonacci naive version:

// Time: O(2^n) — คำนวณซ้ำเยอะมาก
// Space: O(n) — call stack ลึกสุด n ชั้น ไม่ใช่ O(1) นะ!
function fibonacci(n: number): number {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

หลายคนมองข้าม space ของ recursive function ไปครับ แต่จริงๆ ทุก function call มันกิน slot บน call stack — และ naive fibonacci จะ recursive ลึกสุด n ชั้น นั่นแปลว่า space complexity คือ O(n) ไม่ใช่ O(1) แล้ว memoization version ล่ะ?

// Time: O(n) — คำนวณแต่ละค่าครั้งเดียว
// Space: O(n) — memo object + call stack รวมกัน ยังคงเป็น O(n)
function fibonacci(n: number, memo: Record<number, number> = {}): number {
  if (n <= 1) return n;
  if (n in memo) return memo[n]; // ✅ ใช้ 'in' แทน falsy check
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

เร็วขึ้นจาก O(2^n) → O(n) แต่ space ยังคง O(n) เหมือนเดิม — เพราะเราแลก time มาด้วยการเก็บ memo ไว้นั่นเอง 😅

Visualize Big O Notation

เพื่อให้เห็นภาพชัดเจนขึ้น ผมได้สร้างกราฟที่แสดงการเติบโตของฟังก์ชันต่างๆ ตาม Big O Notation ซึ่งจะช่วยให้เราเข้าใจได้ง่ายขึ้นว่าแต่ละฟังก์ชันเติบโตอย่างไรเมื่อขนาดของ input เพิ่มขึ้น ลองเล่นๆ ดูได้เลยครับ!