Big O — Complexity Analysis

Big O: vì sao O(n²) chạy tốt khi demo rồi sập khi dữ liệu lớn

Big O mô tả độ phức tạp của thuật toán tăng theo kích thước input như thế nào — không phải thời gian tuyệt đối, mà tốc độ tăng. Đây là công cụ để dự đoán code sẽ giữ vững hay sập khi dữ liệu lớn lên, trước khi nó xảy ra trong production. Lý do thực tế: một thuật toán O(n²) chạy mượt với 100 phần tử lúc dev (10.000 thao tác) nhưng với 100.000 phần tử ở production là 10 tỷ thao tác — CPU spike, request timeout. Hiểu Big O biến "tự dưng chậm khi nhiều dữ liệu" thành thứ đoán trước được và chữa được bằng cách đổi cấu trúc dữ liệu.

Cơ chế hoạt động

Big O đếm thao tác theo n (kích thước input), bỏ qua hằng số và số hạng bậc thấp. Các bậc thường gặp, từ tốt tới xấu: O(1) hằng số, O(log n) tìm kiếm nhị phân, O(n) duyệt một lần, O(n log n) sort, O(n²) vòng lặp lồng, O(2ⁿ) đệ quy phân nhánh.

// O(n²): với mỗi phần tử, quét lại cả mảng tìm trùng
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true
  return false
}

// O(n): dùng Set, đổi việc "tìm trong mảng" O(n) thành "tra Set" O(1)
function hasDuplicate(arr) {
  const seen = new Set()
  for (const x of arr) {
    if (seen.has(x)) return true // tra O(1)
    seen.add(x)
  }
  return false
}

Mấu chốt phổ biến nhất: một vòng lặp lồng để tìm kiếm bên trong thường là O(n²), và gần như luôn hạ được xuống O(n) bằng một Set/Map (hash) — đổi việc dò tuyến tính thành tra cứu hằng số. Cùng kết quả, khác hẳn về khả năng chịu tải.

Vấn đề gặp trong production

Failure mode: O(n²) ẩn trong vòng lặp lồng. Lỗi hiệu năng phổ biến nhất ở backend: với mỗi phần tử của danh sách A, tìm phần tử tương ứng trong danh sách B bằng find/includes/filter:

// O(n*m): với mỗi order, quét toàn bộ users để tìm tên -> sập khi cả hai lớn
const result = orders.map(o => ({ ...o, userName: users.find(u => u.id === o.userId).name }))

// O(n+m): dựng Map một lần, tra O(1)
const userMap = new Map(users.map(u => [u.id, u]))
const result = orders.map(o => ({ ...o, userName: userMap.get(o.userId)?.name }))

.find bên trong .map là dấu hiệu kinh điển — nó ẩn một vòng lặp lồng. Với dữ liệu test nhỏ không thấy gì; với dữ liệu thật, thời gian tăng theo bình phương.

Failure mode: tối ưu sai chỗ (premature optimization). Ngược lại, vi chỉnh một đoạn O(n) chạy một lần lúc khởi động, hay đổi code rõ ràng thành code khó đọc để tiết kiệm vài mili-giây ở chỗ không nóng, là phí công và thêm rủi ro bug. Big O chỉ quan trọng ở nơi n lớn và tăng; với n nhỏ cố định, hằng số và độ dễ đọc quan trọng hơn bậc.

Failure mode: bỏ qua space complexity. Đôi khi đổi thời gian lấy bộ nhớ (dựng Map để tra nhanh tốn RAM bằng kích thước dữ liệu). Với dữ liệu rất lớn, một giải pháp O(n) thời gian nhưng O(n) bộ nhớ có thể OOM — cần cân cả hai trục.

Cách debug và monitor

Khi một endpoint chậm dần theo lượng dữ liệu (nhanh trên staging, chậm trên production), nghi ngay một bậc phức tạp xấu — đo thời gian theo kích thước input thực tế, nếu thời gian tăng theo bình phương khi n gấp đôi thì là O(n²). Tìm trong code các vòng lặp lồng và đặc biệt .find/.includes/.indexOf bên trong .map/.forEach/vòng lặp — đó là O(n²) trá hình. Profiler (CPU flame graph) chỉ ra hàm chiếm thời gian; nếu nó là một vòng lặp tìm kiếm, hạ bằng hash. Theo dõi độ trễ theo phân vị (p99) khi dữ liệu tăng — bậc xấu lộ ra ở đuôi trước. Đừng tối ưu khi chưa đo: xác định hot path bằng profiler thật rồi mới sửa.

Tradeoff

Thuật toán bậc thấp hơn (O(n) thay O(n²)) chịu tải tốt hơn nhiều khi dữ liệu lớn — đây là khác biệt giữa "giữ được" và "sập". Cái giá đôi khi là code phức tạp hơn (dựng cấu trúc phụ) và tốn bộ nhớ hơn (đổi time lấy space). Nhưng tối ưu sai chỗ — vi chỉnh nơi n nhỏ hoặc không nóng — chỉ thêm độ khó đọc và rủi ro mà không lợi. Quy tắc thực tế: viết code rõ ràng trước; đo để tìm hot path thật; ở hot path có n lớn, ưu tiên hạ bậc (vòng lặp lồng → hash); cân cả space khi dữ liệu rất lớn; và bỏ qua tối ưu ở chỗ n nhỏ cố định nơi độ dễ đọc đáng giá hơn.

Câu hỏi phỏng vấn

Làm sao HashMap giảm một thuật toán từ O(n²) xuống O(n), và khi nào KHÔNG nên tối ưu?

Một thuật toán O(n²) điển hình là vòng lặp lồng để tìm kiếm: với mỗi phần tử của danh sách A, quét tuyến tính danh sách B (find/includes) — mỗi lần tìm tốn O(n), nhân với n phần tử thành O(n²). HashMap/Set hạ xuống O(n) bằng cách dựng một bảng tra một lần (O(n)) rồi mỗi lần tìm chỉ tốn O(1), tổng O(n+m): đổi "dò tuyến tính lặp lại" thành "tra cứu hằng số". Đây là vì sao .find bên trong .map nên thay bằng Map.get. KHÔNG nên tối ưu khi n nhỏ và cố định hoặc đoạn code không nằm trên hot path — vi chỉnh ở đó chỉ làm code khó đọc và thêm rủi ro mà không cải thiện thực tế (premature optimization); ưu tiên độ rõ ràng, đo bằng profiler để tìm hot path thật rồi mới sửa. Điểm ăn điểm: cân cả space complexity (dựng Map tốn RAM, dữ liệu rất lớn có thể OOM) và theo dõi độ trễ p99 khi dữ liệu tăng vì bậc xấu lộ ở đuôi trước.

Hands-on

Lấy một đoạn ghép dữ liệu thật có .find/.includes bên trong .map (ví dụ gắn tên user vào danh sách order, hoặc tìm trùng trong một danh sách) và đo thời gian chạy với n = 1.000, 10.000, 100.000 để thấy thời gian tăng theo bình phương. Refactor bằng cách dựng một Map tra cứu một lần và đo lại để thấy nó tăng tuyến tính. Dùng profiler để xác nhận hot path là vòng lặp tìm kiếm trước khi sửa. Cuối cùng, đo cả bộ nhớ của bản dùng Map trên dữ liệu rất lớn để thấy đánh đổi time-space, và tạo một ví dụ ngược (tối ưu một đoạn n nhỏ không nóng) để cảm nhận premature optimization làm code khó đọc mà không lợi.