Độ phức tạp thuật toán & Big-O từ căn bản

1. Complexity thực sự đo gì?

Đừng bắt đầu bằng câu “O(n) nghĩa là chậm”. Hãy bắt đầu bằng câu hỏi: khi input lớn lên thì chi phí tăng theo tốc độ nào? Ta cố tình bỏ qua máy tính cụ thể, JVM cụ thể và số mili-giây tại một lần chạy để nhìn vào growth rate — tốc độ tăng.

static int first(int[] values) {
    return values[0];
}

Dù array có 10 hay 10 triệu phần tử, method trên vẫn truy cập một vị trí. Chi phí không tăng theo số phần tử nên ta gọi là O(1). O(1) không có nghĩa đúng một CPU instruction; nó chỉ nghĩa chi phí bị chặn bởi một hằng số không phụ thuộc n.

static boolean contains(int[] values, int target) {
    for (int value : values) {
        if (value == target) return true;
    }
    return false;
}

Nếu n = values.length, worst case phải kiểm tra tất cả n phần tử. Lượng công việc tăng tuyến tính theo n, nên worst-case running time là O(n).

2. Big-O, Ω và Θ: đừng học sai ngay từ đầu

Trong phỏng vấn, mọi người thường dùng “Big-O” như cách nói chung về complexity. Điều đó phổ biến, nhưng về mặt toán học nên nhớ: O là upper bound. MIT và Cornell đều trình bày asymptotic notation theo hướng này. Vì vậy câu “Big-O là worst case” là cách nói tắt không chính xác.

3. Vì sao bỏ constant và lower-order terms?

Asymptotic analysis quan tâm tốc độ tăng khi n lớn. Các hệ số cố định và thành phần bậc thấp dần ít quyết định hình dạng tăng trưởng.

Không phải vì constant “không bao giờ quan trọng”. Trong production, constant factor, CPU cache, allocation, JIT, database/network I/O có thể ảnh hưởng mạnh. Ta bỏ chúng trong asymptotic model để so tốc độ tăng trưởng, sau đó benchmark/profiling mới trả lời runtime thực tế.

4. Các mức complexity thường gặp

5. Đọc complexity từ code Java

Một vòng lặp

for (int i = 0; i < n; i++) {
    work();
}

Nếu work() là constant time, vòng lặp chạy n lần → O(n).

Hai vòng nối tiếp: cộng, không nhân

for (int i = 0; i < n; i++) workA();
for (int i = 0; i < n; i++) workB();

n + n = 2n → O(n), không phải O(n²).

Hai vòng lồng nhau: thường nhân

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        compare(i, j);
    }
}

n × n = n² → O(n²).

Chia đôi mỗi bước: logarithmic

for (int x = n; x > 1; x /= 2) {
    work();
}

Sau k bước ta có xấp xỉ n / 2^k = 1, nên k ≈ log₂ n → O(log n).

6. Time Complexity và Space Complexity

Time complexity mô tả lượng công việc tăng thế nào. Space complexity mô tả bộ nhớ cần dùng tăng thế nào. Trong interview nên nói rõ bạn đang tính auxiliary space (bộ nhớ phụ do thuật toán cấp thêm) hay tổng không gian bao gồm input.

static long sum(int[] values) {
    long total = 0;
    for (int value : values) total += value;
    return total;
}

Với n = values.length: time O(n), auxiliary space O(1).

static int[] copy(int[] values) {
    return java.util.Arrays.copyOf(values, values.length);
}

Copy n phần tử cần time O(n) và tạo array mới kích thước n → auxiliary space O(n).

7. Best case, Average case, Worst case

Đây là ba cách chọn tình huống/input để phân tích cùng một thuật toán.

Một thuật toán có thể có nhiều case khác nhau, và mỗi case lại có thể được mô tả bằng O/Ω/Θ. Do đó không ghép cứng “O = worst, Ω = best”.

8. Amortized complexity: vì sao ArrayList.add() vẫn được gọi O(1)?

Amortized analysis nhìn chi phí trung bình trên một chuỗi operation, không phải xác suất average-case của input. Một operation riêng lẻ có thể đắt, nhưng nếu operation đắt xảy ra thưa và được phân bổ trên nhiều operation rẻ, chi phí amortized vẫn thấp.

ArrayList dùng backing array có capacity. Phần lớn add(e) chỉ ghi vào vị trí trống. Khi hết capacity, implementation phải tăng storage và copy phần tử — lần đó có thể tốn tuyến tính. Tuy nhiên Java API contract nêu rõ add có amortized constant time: thêm n phần tử cần tổng thời gian O(n).

9. Nối kiến thức Big-O sang Java Collections

Bảng dưới là cầu nối để bạn hiểu các chapter Collections tiếp theo. Hãy đọc API contract thay vì thuộc một bảng complexity không có điều kiện.

10. Phỏng vấn: cách tự phân tích thay vì học thuộc

Khung trả lời 5 bước

1. Xác định input size: n là gì? Có cần thêm m, V, E không?
2. Chọn case: best, average hay worst? Có giả định xác suất nào không?
3. Đếm growth: operation nào lặp theo input; nối tiếp thì cộng, lồng nhau thường nhân, chia nhỏ thì xét số tầng.
4. Rút gọn: bỏ constant và lower-order terms.
5. Nói cả space/trade-off: nếu bài toán yêu cầu.

Câu hỏi nhanh

Bài tập tự tính

// A
for (int i = 0; i < n; i++) { work(); }
for (int j = 0; j < n; j++) { work(); }

// B
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) { work(); }
}

// C
for (int i = 1; i < n; i *= 2) { work(); }