Phỏng vấn

Cách phân tích Time và Space Complexity khi phỏng vấn: Tránh các bẫy ngầm kinh điển

Trong mọi buổi phỏng vấn thuật toán tại các công ty công nghệ, viết xong code chạy đúng mới chỉ đi được 70% quãng đường. Câu hỏi chắc chắn xuất hiện ngay sau đó là: "Độ phức tạp thời gian và bộ nhớ của lời giải này là bao nhiêu, và vì sao?". Rất nhiều ứng viên mất điểm đáng tiếc vì thói quen đếm số vòng lặp lồng nhau một cách máy móc.

Ý chính
  • Tuyệt đối không kết luận "hai vòng lặp lồng nhau là \(\mathcal{O}(N^2)\)": các mẫu Hai con trỏ (Two Pointers), Cửa sổ trượt (Sliding Window) và Ngăn xếp đơn điệu (Monotonic Stack) đều có vòng while bên trong vòng for nhưng tổng thời gian chỉ là \(\mathcal{O}(N)\) nhờ phân tích khấu hao (Amortized Analysis).
  • Vòng lặp duyệt qua các bội số for (i = 1..N) for (j = i..N; j += i) có độ phức tạp là \(\mathcal{O}(N \log N)\) theo chuỗi điều hòa, không phải \(\mathcal{O}(N^2)\).
  • Khi tính Độ phức tạp Không gian phụ trợ (Auxiliary Space Complexity), bắt buộc phải cộng cả chiều sâu ngăn xếp lời gọi đệ quy (Call Stack Depth) và bộ nhớ cấp phát ngầm khi cắt chuỗi (substring / slicing).
  • Luôn định nghĩa rõ các biến số trong ký hiệu Big-O (ví dụ: trên đồ thị phải ghi \(\mathcal{O}(V + E)\) thay vì \(\mathcal{O}(N)\) mơ hồ; với mảng chuỗi phải tách rõ số chuỗi \(N\) và độ dài chuỗi tối đa \(L\)).

Khung 3 bước trình bày Big-O thuyết phục người phỏng vấn

Nếu bạn đã nắm vững kiến thức nền tảng từ bài tìm kiếm nhị phân cùng bảng băm (Hash Table), mục tiêu khi bước vào phòng phỏng vấn không chỉ là đọc ra đáp số cuối cùng mà là diễn giải quá trình suy luận rõ ràng trong 30–45 giây. Hãy áp dụng cấu trúc 3 câu sau:

  1. Câu 1 — Định nghĩa biến đầu vào: Nêu rõ từng ký hiệu bạn sắp dùng đại diện cho đại lượng nào. Ví dụ: "Gọi \(N\) là số lượng từ trong danh sách và \(L\) là độ dài lớn nhất của một từ."
  2. Câu 2 — Bóc tách từng giai đoạn của hàm: Cộng độ phức tạp của các bước nối tiếp nhau và nhân (hoặc tính tổng khấu hao) cho các bước lồng nhau. Ví dụ: "Bước sắp xếp mảng đầu vào tốn \(\mathcal{O}(N \log N)\) phép so sánh; mỗi phép so sánh hai chuỗi dài \(L\) tốn \(\mathcal{O}(L)\), nên bước sắp xếp tốn \(\mathcal{O}(N \cdot L \log N)\)."
  3. Câu 3 — Tách bạch Không gian phụ trợ (Auxiliary Space) và Không gian đầu ra (Output Space): Người phỏng vấn rất thích ứng viên phân biệt rõ: "Nếu không tính mảng kết quả bắt buộc phải trả về theo yêu cầu đề bài, thuật toán chỉ dùng \(\mathcal{O}(1)\) bộ nhớ phụ trợ; nếu tính cả ngăn xếp đệ quy trên cây nhị phân có chiều cao \(H\), bộ nhớ phụ là \(\mathcal{O}(H)\), tức \(\mathcal{O}(\log N)\) khi cây cân bằng và \(\mathcal{O}(N)\) khi cây suy biến."

5 cái bẫy phân tích Time Complexity hay làm ứng viên trả lời sai nhất

Trong các buổi phỏng vấn theo lộ trình luyện LeetCode phỏng vấn Big Tech, người phỏng vấn thường cố tình cài các cấu trúc vòng lặp hoặc lời gọi thư viện dưới đây để kiểm tra xem ứng viên có thực sự hiểu bản chất toán học hay không:

Bẫy 1: Hai vòng lặp lồng nhau nhưng tổng số bước chỉ là O(N) (Amortized Analysis)

Xét đoạn mã tìm phần tử lớn hơn tiếp theo bằng ngăn xếp đơn điệu hoặc thu hẹp cửa sổ trượt:

int left = 0;
for (int right = 0; right < n; ++right) {
    window_sum += a[right];
    while (window_sum > target && left <= right) {
        window_sum -= a[left];
        left++;
    }
}

Nhiều ứng viên nhìn thấy while nằm trong for liền trả lời vội là \(\mathcal{O}(N^2)\). Thực tế, biến left khởi tạo bằng \(0\), chỉ tăng tiến (left++) chứ không bao giờ đặt lại (reset) về 0 ở mỗi vòng right. Trong suốt toàn bộ quá trình chạy của hàm, left chỉ tăng tối đa \(N\) lần và right tăng đúng \(N\) lần. Tổng số phép toán cộng trừ không vượt quá \(2N = \mathcal{O}(N)\).

Bẫy 2: Vòng lặp bước nhảy bội số (Chuỗi điều hòa O(N log N))

Xét đoạn mã rất quen thuộc trong sàng ước số hoặc quy hoạch động trên bội số:

for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; j += i) {
        cnt[j]++;
    }
}

Ở đây bước nhảy của vòng lặp trong là j += i chứ không phải j++. Số lần thực thi của vòng lặp trong ứng với từng giá trị \(i\) lần lượt là \(\lfloor \frac{N}{1} \rfloor + \lfloor \frac{N}{2} \rfloor + \lfloor \frac{N}{3} \rfloor + \dots + \lfloor \frac{N}{N} \rfloor\). Đặt \(N\) làm nhân tử chung: \[T(N) \le N \sum_{i=1}^{N} \frac{1}{i} = N \cdot H_N = \mathcal{O}(N \log N)\] vì tổng chuỗi điều hòa thứ \(N\) hội tụ tiệm cận theo lô-ga-rít tự nhiên: \(H_N = \ln N + \gamma + \mathcal{O}(\frac{1}{N})\).

Phân tích Độ phức tạp: Vòng lặp điều hòa O(N log N) vs Hai con trỏ O(N) Với N = 8: Tổng số bước nhảy bội số j += i là 8 + 4 + 2 + 2 + 1 + 1 + 1 + 1 = 20 phép toán 1. Lưới bội số (for i=1..N; for j=i..N step i) i = 1: j = 1,2,3,4,5,6,7,8 (8 bước) i = 2: j = 2,4,6,8 (4 bước) i = 3: j = 3,6 (2 bước) i = 4: j = 4,8 (2 bước) i = 5..8: mỗi vòng đúng (1 bước x 4) Tổng ≤ N(1 + 1/2 + 1/3 + ... + 1/N) Chuỗi điều hòa H_N ~ ln(N) -> O(N log N)! 2. Khấu hao (Amortized) O(N) với Ngăn xếp Mỗi phần tử A[i] trong N = 8 phần tử: • Được push() vào stack đúng 1 lần (8 lần) • Bị pop() khỏi stack tối đa 1 lần (7 lần) Tổng thao tác = 8 + 7 = 15 <= 2N Dù có while bên trong for, độ phức tạp vẫn là O(N).
Bẫy phân tích Big-O phỏng vấn Không phải cứ 2 vòng lặp lồng nhau là O(N^2) 1. Bước nhảy bội số (j += i) N = 8: 8 + 4 + 2 + 2 + 1 + 1 + 1 + 1 = 20 Chặn trên: N * H_N (chuỗi điều hòa) -> Độ phức tạp: O(N log N) Không phải O(N^2) như nhiều ứng viên nhầm! 2. Hai con trỏ / Ngăn xếp đơn điệu N = 8: 8 lệnh push + 7 lệnh pop = 15 Mỗi phần tử vào 1 lần, ra tối đa 1 lần -> Độ phức tạp: O(N) (Amortized O(1)) Tổng số bước nội bộ không vượt quá 2N.
Hình 1: Đối chiếu trực quan với N = 8: vòng lặp bội số chỉ tốn 20 bước theo chuỗi điều hòa O(N log N), còn ngăn xếp đơn điệu chỉ tốn tối đa 2N - 1 = 15 thao tác đẩy/lấy O(N).

Bẫy 3: Chi phí ẩn của thao tác Cắt chuỗi và Nối chuỗi trong vòng lặp

Trong Python (s = s + ch hoặc s[i:j]), Java (String bất biến) và C++ (s.substr(i, len)), việc cắt một chuỗi con dài \(K\) hoặc nối thêm ký tự vào một chuỗi bất biến không phải là \(\mathcal{O}(1)\) mà tốn \(\mathcal{O}(K)\) thời gian và \(\mathcal{O}(K)\) bộ nhớ mới để sao chép mảng ký tự. Nếu bạn đặt s.substr(0, i) bên trong một vòng lặp chạy \(N\) lần, độ phức tạp đã âm thầm nhảy từ \(\mathcal{O}(N)\) lên \(\mathcal{O}(N^2)\).

Bẫy 4: Độ phức tạp của Đệ quy Quay lui (Backtracking) và Cây phân nhánh

Khi phân tích hàm đệ quy có hệ số phân nhánh \(b\) (mỗi lời gọi sinh ra tối đa \(b\) lời gọi con) và độ sâu tối đa của cây đệ quy là \(d\), số nút trên cây đệ quy bị chặn bởi \(\mathcal{O}(b^d)\). Tuy nhiên, đừng quên nhân thêm chi phí xử lý tại mỗi nút lá! Chẳng hạn khi sinh mọi hoán vị của mảng \(N\) phần tử, có \(N!\) nút lá và tại mỗi nút lá bạn phải sao chép mảng kết quả dài \(N\) phần tử vào danh sách trả về, nên tổng thời gian thực tế là \(\mathcal{O}(N \cdot N!)\) chứ không chỉ là \(\mathcal{O}(N!)\).

Bẫy 5: Xây dựng Heap bằng heapify (O(N)) so với đẩy từng phần tử (O(N log N))

Nếu bạn đẩy lần lượt \(N\) phần tử vào một hàng đợi ưu tiên rỗng, chi phí là \(\mathcal{O}(N \log N)\). Nhưng nếu đưa cả mảng \(N\) phần tử có sẵn vào hàm std::make_heap (C++) hoặc heapq.heapify(arr) (Python) theo thuật toán Floyd đi từ tầng sát đáy lên gốc, phần lớn các nút nằm ở đáy cây chỉ dịch chuyển tối đa 1–2 bậc, nên tổng thời gian hội tụ về tuyến tính: \[\sum_{h=0}^{\lfloor \log_2 N \rfloor} \frac{N}{2^{h+1}} \cdot \mathcal{O}(h) = \mathcal{O}(N)\]

Chạy tay (Dry-run) đếm số phép toán chính xác trên 4 mẫu vòng lặp

Để kiểm chứng sự chênh lệch giữa 4 cấu trúc vòng lặp phổ biến, hãy xét đầu vào cụ thể \(N = 8\) và đếm chính xác số phép toán cơ sở thực thi:

Mẫu thuật toán Công thức số phép toán với \(N\) tổng quát Thay số với \(N = 8\) Số bước thực tế Ký hiệu Big-O chuẩn
1. Thu hẹp khoảng chia đôi (while m > 0: m //= 2) \(\lfloor \log_2 N \rfloor + 1\) \(8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 0\) \(4\text{ bước}\) \(\mathcal{O}(\log N)\)
2. Lưới bội số điều hòa (for i=1..N; for j=i..N step i) \(\sum_{i=1}^{N} \lfloor \frac{N}{i} \rfloor\) \(8 + 4 + 2 + 2 + 1 + 1 + 1 + 1\) \(20\text{ bước}\) \(\mathcal{O}(N \log N)\)
3. Ngăn xếp đơn điệu / 2 con trỏ (\(N\) lần push, \(N-1\) lần pop) \(N + (N - 1) = 2N - 1\) \(8\text{ lần đẩy} + 7\text{ lần lấy}\) \(15\text{ bước}\) \(\mathcal{O}(N)\)
4. Cặp chỉ số phân biệt (for i=0..N-1; for j=i+1..N-1) \(\frac{N(N - 1)}{2}\) \(\frac{8 \times 7}{2}\) \(28\text{ bước}\) \(\mathcal{O}(N^2)\)

Khi \(N\) tăng từ \(8\) lên \(1{,}000\), mẫu số 2 (Chuỗi điều hòa) chỉ thực hiện 7,069 bước, mẫu số 3 (Hai con trỏ) thực hiện 1,999 bước, trong khi mẫu số 4 (Cặp đôi vét cạn) vọt lên tới 499,500 bước! Chương trình dưới đây (C++17, Python, Java 21) chạy thật 4 vòng lặp và đếm số bước của từng mẫu; mẫu 3 dùng ngăn xếp đơn điệu tìm phần tử lớn hơn tiếp theo trên mảng tăng dần \(1, 2, \dots, N\), đúng trường hợp \(N\) lần đẩy và \(N - 1\) lần lấy ra. Chạy không có đầu vào, chương trình đếm cho \(N = 8\) và \(N = 1{,}000\) rồi in N = 8: 4 20 15 28 và N = 1000: 10 7069 1999 499500, khớp các số ở trên:

// Chạy thật 4 mẫu vòng lặp của bảng "Chạy tay" và đếm số bước của từng mẫu, để so với công thức trong bảng.
// Đầu vào: một hoặc nhiều số N >= 1. Không có đầu vào thì đếm cho N = 8 và N = 1000 như trong bài.
// Mỗi dòng in: N = <N>: <mẫu 1> <mẫu 2> <mẫu 3> <mẫu 4>. Bộ đếm dùng long long vì mẫu 4 có N(N - 1) / 2 bước.
#include <iostream>
#include <vector>
using namespace std;

long long dem_chia_doi(long long n) {  // Mẫu 1: while m > 0: m /= 2 (công thức: floor(log2 N) + 1)
    long long buoc = 0;
    for (long long m = n; m > 0; m /= 2) ++buoc;
    return buoc;
}

long long dem_boi_so(long long n) {  // Mẫu 2: for i = 1..N, for j = i; j <= N; j += i (công thức: tổng các N / i)
    long long buoc = 0;
    for (long long i = 1; i <= n; ++i)
        for (long long j = i; j <= n; j += i) ++buoc;
    return buoc;
}

long long dem_ngan_xep(long long n) {  // Mẫu 3: ngăn xếp đơn điệu trên mảng tăng 1, 2, ..., N (công thức: 2N - 1)
    vector<long long> st;
    long long buoc = 0;
    for (long long x = 1; x <= n; ++x) {
        while (!st.empty() && st.back() < x) {
            st.pop_back();  // một lần lấy ra
            ++buoc;
        }
        st.push_back(x);  // một lần đẩy vào
        ++buoc;
    }
    return buoc;
}

long long dem_cap(long long n) {  // Mẫu 4: for i = 0..N-1, for j = i+1..N-1 (công thức: N(N - 1) / 2)
    long long buoc = 0;
    for (long long i = 0; i < n; ++i)
        for (long long j = i + 1; j < n; ++j) ++buoc;
    return buoc;
}

int main() {
    vector<long long> ns;
    long long n;
    while (cin >> n) ns.push_back(n);
    if (ns.empty()) ns = {8, 1000};
    for (long long v : ns)
        cout << "N = " << v << ": " << dem_chia_doi(v) << " " << dem_boi_so(v) << " " << dem_ngan_xep(v) << " "
             << dem_cap(v) << "\n";
    return 0;
}

Bảng tra nhanh từ giới hạn đề bài sang độ phức tạp mục tiêu

Khi luyện tập cũng như khi thi Online Assessment, máy chấm thường giới hạn khoảng \(10^8\) phép toán cơ bản mỗi giây. Nhìn vào ràng buộc của \(N\), bạn có thể suy ngược ngay thuật toán cần tìm:

Ràng buộc kích thước \(N\) Độ phức tạp tối đa cho phép Các hướng tiếp cận thuật toán điển hình
\(N \le 11\) \(\mathcal{O}(N!)\), \(\mathcal{O}(N \cdot N!)\) Sinh hoán vị, vét cạn nhánh cận (Branch and Bound)
\(N \le 20\) \(\mathcal{O}(2^N)\), \(\mathcal{O}(N \cdot 2^N)\) Quay lui nhị phân, Quy hoạch động trạng thái bit (Bitmask DP)
\(N \le 500\) \(\mathcal{O}(N^3)\) Thuật toán Floyd-Warshall, Quy hoạch động trên đoạn \([l, r]\)
\(N \le 5{,}000\) \(\mathcal{O}(N^2)\) Quy hoạch động 2 chiều cơ bản, Duyệt tâm mở rộng hai phía
\(N \le 2 \times 10^5\) \(\mathcal{O}(N \log N)\) hoặc \(\mathcal{O}(N)\) Sắp xếp + Hai con trỏ, Chia để trị, Heap, Cây phân đoạn, Bảng băm
\(N \le 10^7\) \(\mathcal{O}(N)\) Quét một lượt tuyến tính, Sàng nguyên tố tuyến tính, Mảng cộng dồn
\(N \ge 10^9\) (tới \(10^{18}\)) \(\mathcal{O}(\log N)\) hoặc \(\mathcal{O}(\sqrt{N})\) Tìm kiếm nhị phân, Lũy thừa nhị phân ma trận, Toán số học

Luyện ngay trên Big-O Coding

Để rèn phản xạ tối ưu cả thời gian lẫn không gian phụ trợ — từ xoay mảng tại chỗ với \(\mathcal{O}(1)\) bộ nhớ, tìm kiếm \(\mathcal{O}(\log N)\) đến đệ quy trên cây trong \(\mathcal{O}(N)\) — hãy thử sức ngay với 3 bài toán kinh điển dưới đây:

Độ phức tạp của việc tra cứu và thêm phần tử vào Bảng băm (unordered_map, dict, HashMap) khi phỏng vấn nên trả lời là gì?

Câu trả lời chuẩn xác nhất là: Trung bình \(\mathcal{O}(1)\) (Amortized Average Case), và trường hợp xấu nhất là \(\mathcal{O}(N)\) khi tất cả các khóa bị đụng độ rơi vào cùng một thùng chứa (Bucket) — hoặc \(\mathcal{O}(\log N)\) trong Java 8+ khi danh sách liên kết trong thùng tự động chuyển thành Cây Đỏ-Đen (Red-Black Tree) lúc vượt ngưỡng 8 phần tử. Nêu được chi tiết này sẽ khiến người phỏng vấn đánh giá rất cao kiến thức nền tảng của bạn.

Sắp xếp mảng N phần tử tốn bao nhiêu bộ nhớ phụ trợ (Space Complexity)?

Không phải mọi hàm sort() thư viện đều dùng \(\mathcal{O}(1)\) bộ nhớ!

  • Trong C++ (std::sort — Introsort): kết hợp QuickSort, HeapSort và InsertionSort, tốn \(\mathcal{O}(\log N)\) bộ nhớ trên ngăn xếp đệ quy.
  • Trong Python (Timsort) và Java (Timsort cho mảng đối tượng Object[]): cần mảng đệm để trộn các đoạn con tăng dần, tốn tới \(\mathcal{O}(N)\) bộ nhớ phụ trợ trong trường hợp xấu nhất.
Khi đệ quy trên cây nhị phân có N nút, tại sao không được nói luôn Space Complexity là O(log N)?

Bởi vì một cây nhị phân bất kỳ không có gì đảm bảo là cây cân bằng! Nếu cây bị lệch hẳn về một phía giống danh sách liên kết đơn (Skewed Tree), chiều cao của cây là \(H = N\), khiến ngăn xếp lời gọi đệ quy chiếm \(\mathcal{O}(N)\) bộ nhớ. Do đó, bạn phải nói: "Bộ nhớ phụ là \(\mathcal{O}(H)\) với \(H\) là chiều cao của cây: bằng \(\mathcal{O}(\log N)\) khi cây cân bằng và \(\mathcal{O}(N)\) trong trường hợp cây suy biến."

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483