Big-O & Phân tích
độ phức tạp

1.1 Tại sao cần Big-O?

Hãy tưởng tượng bạn viết hai hàm findUser đều "đúng" — đều trả về user theo email. Nhưng cách thứ nhất chạy 0.001 giây, cách thứ hai chạy 4 giây khi database có 1 triệu user. Cả hai đều đúng logic. Khác biệt nằm ở độ phức tạp thuật toán.

Big-O là cách diễn đạt tốc độ tăng của thuật toán theo kích thước input — không quan tâm máy tính nhanh hay chậm, không quan tâm ngôn ngữ là JS hay C, chỉ quan tâm: khi n tăng gấp đôi, thời gian chạy tăng bao nhiêu lần?

Câu chuyện n = 1 triệu

Giả sử máy bạn chạy 10⁸ phép tính/giây. Đây là thời gian thực tế để xử lý n = 1,000,000:

Nhìn bảng này, bạn sẽ hiểu vì sao phỏng vấn luôn hỏi "Big-O của giải pháp này là gì?". Câu trả lời O(n²) với input lớn = bài làm không pass.

1.2 Định nghĩa Big-O

Định nghĩa toán học (đơn giản hoá cho lập trình viên):

Nói nôm na:

• Big-O là cận trên của tốc độ tăng (worst case).
• Khi n đủ lớn, f(n) không tăng nhanh hơn g(n) theo bậc.
• Hằng số c để "bỏ qua" phần multiply nhỏ — vì lúc n lớn, hằng số không quan trọng.

Ví dụ trực quan

function sumArray(arr) {
  let total = 0;        // 1 bước
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];    // n bước
  }
  return total;         // 1 bước
}

Tổng số phép tính: 1 + n + 1 = n + 2. Nhưng Big-O bỏ qua hằng số và chỉ giữ bậc cao nhất → O(n).

1.3 Quy tắc đếm Big-O

Quy tắc 1 — Bỏ hằng số

// Big-O = O(n), không phải O(2n)
function double(arr) {
  for (let i = 0; i < arr.length; i++) console.log(arr[i]);  // n
  for (let i = 0; i < arr.length; i++) console.log(arr[i]);  // n
  // 2n → O(n)
}

Quy tắc 2 — Giữ bậc cao nhất

// Big-O = O(n²), không phải O(n² + n)
function example(arr) {
  for (let i = 0; i < arr.length; i++) {       // n
    for (let j = 0; j < arr.length; j++) {     // n
      console.log(arr[i], arr[j]);              // 1 → tổng n²
    }
  }
  for (let i = 0; i < arr.length; i++) {       // n
    console.log(arr[i]);                         // 1 → tổng n
  }
  // n² + n → O(n²)
}

Quy tắc 3 — Vòng lặp lồng nhau thì NHÂN

// Big-O = O(n²)
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    // ...
  }
}

// Big-O = O(n × m) — KHÁC NHAU khi n và m khác nhau!
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    // ...
  }
}

Quy tắc 4 — Vòng lặp tuần tự thì CỘNG

// Big-O = O(n + m), gộp lại = O(max(n, m))
for (let i = 0; i < n; i++) { /* ... */ }
for (let j = 0; j < m; j++) { /* ... */ }

Quy tắc 5 — Chia đôi thì có log

// Big-O = O(log n) — mỗi vòng n giảm một nửa
let i = n;
while (i > 1) {
  i = Math.floor(i / 2);
  // ...
}

// Binary search là ví dụ kinh điển O(log n)
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

1.4 Các "họ" Big-O — từ tốt nhất đến tệ nhất

Đây là 9 họ Big-O bạn gặp 99% trong phỏng vấn. Học thuộc thứ tự này.

O(1) — Constant

Số phép tính không phụ thuộc kích thước input.

function getFirst(arr) { return arr[0]; }   // O(1)
function isEven(n)     { return n % 2 === 0; } // O(1)

O(log n) — Logarithmic

Mỗi bước, không gian tìm kiếm giảm một nửa. Cực nhanh ngay cả với n khổng lồ.

// Binary search — đã ví dụ ở trên: O(log n)
// Tree traversal trên balanced BST tìm kiếm: O(log n)

O(n) — Linear

Đi qua input đúng 1 lần. Đây là baseline mà mọi giải pháp tốt nên đạt được.

function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}  // O(n)

O(n log n) — Log-linear

Hầu hết thuật toán sort hiệu quả (Merge Sort, Heap Sort, TimSort) đạt mức này. Đây là giới hạn dưới của comparison-based sort.

O(n²) — Quadratic

Hai vòng for lồng nhau. Phải tránh nếu input có thể lớn.

// Bubble sort, selection sort, brute-force two sum
function hasPairSum(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) return true;
    }
  }
  return false;
}  // O(n²)

// Cải tiến với Hash Set → O(n)
function hasPairSumFast(arr, target) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(target - x)) return true;
    seen.add(x);
  }
  return false;
}  // O(n)

O(2ⁿ) — Exponential

Mỗi input mới nhân đôi số trường hợp. Thường xuất hiện trong đệ quy không có memoization.

// Fibonacci đệ quy "ngây thơ" — O(2ⁿ), kinh điển slow
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
// fib(40) đã chậm thấy rõ. fib(60) chạy hàng giờ.

// Cải tiến với memoization → O(n)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

O(n!) — Factorial

Liệt kê mọi hoán vị. Chỉ chạy được khi n ≤ ~10. Bài kinh điển: Travelling Salesman brute force.

1.5 Big-Θ (Theta) và Big-Ω (Omega) — khi nào cần phân biệt?

Trong giao tiếp hàng ngày, lập trình viên dùng "Big-O" cho mọi thứ. Nhưng học thuật phân biệt 3 ký hiệu:

Ví dụ: thuật toán Linear Search:

• Ω(1) — best case: phần tử ở vị trí đầu tiên.
• O(n) — worst case: phần tử ở cuối hoặc không có.
• Không có Θ chặt vì best/worst khác nhau.

Ví dụ: thuật toán tính tổng mảng:

• Ω(n), O(n), Θ(n) — luôn duyệt hết mảng dù sao đi nữa.

1.6 Space Complexity — không chỉ thời gian, còn bộ nhớ

Big-O không chỉ đo thời gian, còn đo bộ nhớ mà thuật toán chiếm. Trong phỏng vấn, hỏi "Time complexity?" thường đi kèm "Space complexity?".

Cách tính space

Space = bộ nhớ thêm mà thuật toán cần (không tính input).

// Time: O(n), Space: O(1)
// Chỉ dùng vài biến cố định, không phụ thuộc n
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) total += arr[i];
  return total;
}

// Time: O(n), Space: O(n)
// Tạo mảng mới có kích thước n
function double(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) result.push(arr[i] * 2);
  return result;
}

Stack space từ đệ quy

Mỗi lời gọi đệ quy chiếm 1 frame trên call stack. Đệ quy sâu n lần → space O(n) ngay cả khi không tạo array nào.

// Time: O(n), Space: O(n) — vì call stack sâu n
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

// Time: O(n), Space: O(1) — phiên bản iterative không tốn stack
function factorialIter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

1.7 Amortized Analysis — "trung bình" thông minh

Đôi khi 1 thao tác đôi lúc chậm, đôi lúc cực nhanh, nhưng trung bình thì nhanh. Đây là amortized analysis (phân tích biên hoá).

Ví dụ kinh điển: Dynamic Array (JS Array)

Khi bạn arr.push(x), hầu hết thời gian là O(1). Nhưng khi mảng đầy, JS engine phải: (1) cấp phát mảng mới gấp đôi kích thước, (2) copy hết phần tử cũ sang. Lúc đó push tốn O(n).

Vậy push() có phải O(n) không?

Vì thế, trong tài liệu của V8 và mọi sách DSA, push được ghi là O(1) amortized.

Ví dụ khác: Hash Table rehashing

Khi load factor vượt ngưỡng (vd 0.75), hash table phải resize và rehash mọi key — O(n). Nhưng amortized cost của insert vẫn là O(1).

1.8 Big-O của các thao tác JavaScript phổ biến

Bảng này bạn nên thuộc lòng. Phỏng vấn rất hay hỏi "Time complexity của arr.includes() là gì?".

Array

Map / Set

String

Demo trực quan — Linear Search vs Binary Search

Tìm số 17 trong mảng đã sort:

Linear search — duyệt từng ô (worst case 8 bước)

Binary search — chia đôi (chỉ 3 bước!)

Bước 1: kiểm tra giữa = 14 → nhỏ hơn 17 → loại nửa trái.

Bước 2: kiểm tra giữa nửa phải = 16 → nhỏ hơn 17 → loại tiếp.

Bước 3: kiểm tra phần tử cuối = 17 → tìm thấy! Tổng 3 bước (log₂ 8 = 3).

Bài tập

Hãy tự tính Big-O trước khi xem đáp án (đáp án ở phần Quiz bên dưới có lời giải).

function f(n) {
  for (let i = 0; i < n; i++) console.log(i);
  for (let j = 0; j < n * n; j++) console.log(j);
}

function f(n) {
  let i = 1;
  while (i < n) {
    console.log(i);
    i *= 2;
  }
}

function f(arr1, arr2) {
  for (const a of arr1) {
    for (const b of arr2) {
      if (a === b) return true;
    }
  }
  return false;
}

function f(n) {
  if (n <= 0) return;
  console.log(n);
  f(n - 1);
  f(n - 1);
}

function f(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j < arr.length; j *= 2) {
      console.log(arr[i], arr[j]);
    }
  }
}

Tổng kết chương 1

• ✅ Big-O đo tốc độ tăng, không phải thời gian tuyệt đối
• ✅ Quy tắc cơ bản: bỏ hằng số, giữ bậc cao nhất
• ✅ Loop lồng nhau → nhân; loop tuần tự → cộng; chia đôi → log
• ✅ Phân biệt time complexity và space complexity (call stack tốn space!)
• ✅ Amortized analysis giải thích vì sao push = O(1) dù đôi khi resize
• ✅ Thuộc lòng Big-O của JS Array/Map/Set built-in — phỏng vấn rất hay hỏi