Login

Big O cho người đi phỏng vấn: cách ước lượng độ phức tạp thuật toán

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Gần như mọi bài thuật toán đều kết thúc bằng câu hỏi: "Độ phức tạp thời gian và bộ nhớ của lời giải này là gì?". Big O không đáng sợ nếu bạn nắm vài quy tắc và nhận ra các mẫu quen thuộc. Bài này giúp bạn ước lượng nhanh và giải thích rõ ràng.

Big O đo cái gì?

Big O mô tả cách chi phí (thời gian hoặc bộ nhớ) tăng theo kích thước đầu vào n khi n lớn, thường xét trường hợp xấu nhất. Nó bỏ qua hằng số và các số hạng nhỏ: 3n + 10 vẫn là O(n), còn n² + n là O(n²). Đây là công cụ so sánh xu hướng, không phải thời gian chạy chính xác.

Các lớp độ phức tạp hay gặp

Ký hiệuTênVí dụ
O(1)Hằng sốTruy cập phần tử mảng theo chỉ số
O(log n)LogaritTìm kiếm nhị phân
O(n)Tuyến tínhDuyệt qua mảng một lần
O(n log n)Tuyến tính logaritSắp xếp hiệu quả như merge sort
O(n²)Bình phươngHai vòng lặp lồng nhau
O(2^n)Hàm mũSinh mọi tập con

Cách đếm nhanh

  • Một vòng lặp qua n phần tử: O(n).
  • Hai vòng lặp lồng nhau cùng chạy tới n: O(n²).
  • Hai vòng lặp nối tiếp nhau (không lồng): O(n + n) = O(n).
  • Mỗi bước giảm một nửa bài toán: O(log n).
  • Đệ quy gọi hai nhánh mỗi lần mà không nhớ kết quả: thường là hàm mũ.

Ví dụ: tìm hai số có tổng bằng target

// Cách 1: hai vòng lặp, O(n^2) thời gian, O(1) bộ nhớfunction twoSumBrute(nums, target) {  for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] + nums[j] === target) return [i, j];    }  }  return null;}// Cách 2: hash map, O(n) thời gian, O(n) bộ nhớfunction twoSum(nums, target) {  const seen = new Map();  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i];    if (seen.has(need)) return [seen.get(need), i];    seen.set(nums[i], i);  }  return null;}

Cách thứ hai đánh đổi bộ nhớ lấy tốc độ. Khi trình bày, hãy nói rõ sự đánh đổi này; đó là điều người phỏng vấn muốn nghe.

Độ phức tạp bộ nhớ

Đừng quên không gian phụ ngoài đầu vào. Tạo một mảng mới kích thước n là O(n) bộ nhớ. Đệ quy sâu d tầng tốn O(d) cho ngăn xếp gọi hàm, nên đệ quy trên danh sách dài có thể gây tràn ngăn xếp. Giải bằng vòng lặp thường tiết kiệm hơn.

Độ phức tạp của các thao tác quen thuộc

  • Sắp xếp bằng thư viện chuẩn: thường O(n log n).
  • Tìm kiếm tuyến tính: O(n); tìm kiếm nhị phân trên mảng đã sắp xếp: O(log n).
  • Thêm vào cuối mảng động: O(1) khấu hao; chèn vào đầu: O(n).
  • Tra cứu hash map: O(1) trung bình.
  • Nối chuỗi trong vòng lặp: có thể là O(n²) nếu mỗi lần tạo chuỗi mới.

Trường hợp tốt nhất, trung bình, xấu nhất

Quick sort trung bình O(n log n) nhưng xấu nhất O(n²) nếu chọn chốt kém. Hash map trung bình O(1) nhưng xấu nhất O(n) nếu nhiều khóa đụng độ. Khi trả lời, hãy nêu rõ bạn đang nói trường hợp nào.

Quy trình trả lời trong phỏng vấn

  1. Nêu lời giải đơn giản nhất và độ phức tạp của nó.
  2. Chỉ ra điểm nghẽn (thường là vòng lặp lồng nhau hoặc tìm kiếm lặp lại).
  3. Đề xuất cấu trúc dữ liệu phù hợp để cải thiện.
  4. Phân tích lại thời gian và bộ nhớ của lời giải mới.

Bài tập nhỏ để tự kiểm tra

Hãy xác định độ phức tạp của đoạn code sau:

function f(n) {  let count = 0;  for (let i = 1; i < n; i *= 2) {    for (let j = 0; j < n; j++) {      count++;    }  }  return count;}

Vòng lặp ngoài nhân đôi i mỗi lần nên chạy khoảng log n lần, vòng trong chạy n lần mỗi lượt. Tổng cộng là O(n log n). Nếu bạn tự suy ra được kết quả này và giải thích bằng lời, bạn đã nắm khá chắc phần phân tích cơ bản. Hãy thử biến đổi đoạn code, chẳng hạn cho j chạy tới i thay vì n, và xem độ phức tạp thay đổi thế nào.

Kết luận

Big O là ngôn ngữ chung để bàn về hiệu quả. Hãy tập gắn độ phức tạp cho mọi hàm bạn viết trong vài tuần, bạn sẽ thấy nó trở thành phản xạ tự nhiên.

Nếu muốn luyện thuật toán có hệ thống từ cơ bản, bạn có thể bắt đầu với các khóa học tại codebem.com.

author_photo
Nguyễn Đình Cường

0 comment