Độ phức tạp thuật toán và ký hiệu Big-O: cách tính nhanh, ví dụ C++ và Python

Vì sao không đo tốc độ thuật toán bằng giây mà dùng Big-O?

Khi mới học lập trình và thuật toán, rất tự nhiên ta muốn bấm đồng hồ xem chương trình chạy hết bao nhiêu mili-giây. Tuy nhiên, thời gian chạy tính bằng giây phụ thuộc vào rất nhiều yếu tố bên ngoài thuật toán: máy tính dùng chip mới hay cũ, trình biên dịch có bật cờ tối ưu -O2 hay không, hoặc lúc đó máy có đang mở nhiều ứng dụng khác hay không.

Để đánh giá công bằng hai cách giải trên mọi máy tính, khoa học máy tính đếm số phép toán cơ bản (cộng, trừ, nhân, chia, so sánh, gán biến, truy cập một ô mảng) theo kích thước đầu vào n. Khi n còn nhỏ (như n = 10), cách làm dở và cách làm hay đều chạy xong trong chớp mắt. Sự khác biệt chỉ bộc lộ rõ rệt khi n tăng lên hàng trăm nghìn hoặc hàng triệu phần tử.

Ký hiệu Big-O (đọc là "O lớn") mô tả tốc độ tăng trưởng của số phép toán trong trường hợp xấu nhất (worst-case) khi n rất lớn.

Cùng một bài toán, ba độ phức tạp khác nhau một trời một vực

Giả sử ta cần tính tổng 1 + 2 + 3 + ... + n với n = 1000. Hãy đặt cạnh nhau 3 cách viết dưới đây và đếm chính xác số lần phép cộng được thực hiện:

#include <iostream>
using namespace std;

// Cách 1: Hai vòng lặp lồng nhau — O(n^2) phép cộng
long long tongCapN2(int n, long long& buoc) {
    long long s = 0;
    buoc = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            s += 1;
            buoc++;
        }
    }
    return s;
}

// Cách 2: Một vòng lặp — O(n) phép cộng
long long tongCapN(int n, long long& buoc) {
    long long s = 0;
    buoc = 0;
    for (int i = 1; i <= n; ++i) {
        s += i;
        buoc++;
    }
    return s;
}

// Cách 3: Công thức cấp số cộng — O(1)
long long tongCapO1(long long n, long long& buoc) {
    buoc = 1;
    return n * (n + 1) / 2;
}

int main() {
    long long b1 = 0, b2 = 0, b3 = 0;
    long long k1 = tongCapN2(1000, b1);
    long long k2 = tongCapN(1000, b2);
    long long k3 = tongCapO1(1000, b3);
    cout << k1 << " " << k2 << " " << k3 << "\n";  // 500500 500500 500500
    cout << b1 << " " << b2 << " " << b3 << "\n";  // 500500 1000 1
    return 0;
}

def tong_cap_n2(n):
    s, buoc = 0, 0
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            s += 1
            buoc += 1
    return s, buoc


def tong_cap_n(n):
    s, buoc = 0, 0
    for i in range(1, n + 1):
        s += i
        buoc += 1
    return s, buoc


def tong_cap_o1(n):
    return n * (n + 1) // 2, 1


k1, b1 = tong_cap_n2(1000)
k2, b2 = tong_cap_n(1000)
k3, b3 = tong_cap_o1(1000)
print(k1, k2, k3)  # 500500 500500 500500
print(b1, b2, b3)  # 500500 1000 1

Cả ba hàm đều in ra kết quả đúng là 500500, nhưng số bước lặp bên trong hoàn toàn khác nhau:

Với n = 100.000, hàm O(n²) phải thực hiện khoảng 5 tỷ phép cộng và bị hệ thống chấm bài báo lỗi quá thời gian (TLE), trong khi hàm O(n) và O(1) trả kết quả ngay lập tức.

Ba quy tắc rút gọn biểu thức Big-O trong 10 giây

Giả sử bạn đếm được một thuật toán thực hiện chính xác T(n) = 4n² + 15n + 200 phép tính. Để suy ra ký hiệu Big-O, bạn chỉ cần áp dụng 3 quy tắc:

1. Quy tắc 1 — Bỏ mọi hằng số nhân: O(7n) viết thành O(n); O(n² / 2) như trong hàm tongCapN2 ở trên (thực hiện n(n + 1) / 2 = 0.5n² + 0.5n bước) cũng viết thành O(n²).
2. Quy tắc 2 — Chỉ giữ lại số hạng có bậc cao nhất: Khi n = 100.000, n² = 10¹⁰ lớn gấp trăm nghìn lần 15n, nên 15n và 200 không còn đáng kể. Do đó 4n² + 15n + 200 rút gọn thành O(n²).
3. Quy tắc 3 — Cộng cho các đoạn nối tiếp, nhân cho các vòng lặp lồng nhau:
   • Hai vòng lặp đứng nối tiếp nhau: vòng đầu chạy O(n), vòng sau chạy O(n log n) → tổng cộng là O(n + n log n) = O(n log n).
   • Hai vòng lặp lồng nhau: vòng ngoài chạy n lần, mỗi lần vòng trong chạy log n bước → tổng cộng là O(n × log n) = O(n log n).

Bảy bậc độ phức tạp thường gặp nhất từ nhanh đến chậm

Hình dưới đây xếp các độ phức tạp phổ biến theo tốc độ tăng của số phép tính khi kích thước dữ liệu n lớn dần:

Để nhận diện nhanh trong code, bạn hãy đối chiếu cách biến chạy thay đổi ở từng vòng lặp:

• O(1) — Độ phức tạp hằng số: Số bước cố định không phụ thuộc n. Ví dụ: truy cập phần tử a[i], kiểm tra chẵn lẻ n % 2 == 0, hoặc tính tổng đoạn bằng mảng cộng dồn sau khi đã tiền xử lý.
• O(log n) — Độ phức tạp logarit: Sau mỗi bước, phạm vi bài toán giảm đi một nửa (hoặc biến chạy nhân đôi x *= 2, chia đôi n /= 2). Với n = 1.024, vòng lặp nhân đôi chỉ chạy đúng 10 lần vì 2¹⁰ = 1024. Tiêu biểu nhất là tìm kiếm nhị phân và thuật toán Euclid tìm ước chung lớn nhất.
• O(√n) — Độ phức tạp căn bậc hai: Vòng lặp chạy với điều kiện i * i <= n. Với n = 1.024, vòng lặp chỉ chạy 32 lần. Thường gặp khi kiểm tra một số nguyên tố hoặc liệt kê các ước số của n.
• O(n) — Độ phức tạp tuyến tính: Duyệt qua từng phần tử của mảng một số lần cố định. Tiêu biểu là tìm kiếm tuần tự, kỹ thuật hai con trỏ và cửa sổ trượt.
• O(n log n) — Tuyến tính nhân logarit: Xuất hiện khi một vòng lặp n lần bao ngoài một thao tác O(log n), hoặc khi chia đôi mảng rồi gộp lại. Đây là độ phức tạp của các thuật toán sắp xếp nhanh như Merge Sort, std::sort (C++) và sorted() (Python).
• O(n²) — Độ phức tạp bậc hai: Hai vòng lặp for lồng nhau cùng chạy từ 1 đến n. Thường gặp ở các thuật toán sắp xếp cơ bản (Bubble Sort, Insertion Sort, Selection Sort) hoặc khi duyệt mọi cặp phần tử (i, j).
• O(2ⁿ) và O(n!) — Độ phức tạp hàm mũ / giai thừa: Số bước tăng bùng nổ khi sinh mọi tập con (2ⁿ) hoặc mọi hoán vị (n!) bằng thuật toán quay lui. Chỉ chạy được khi n rất nhỏ (n ≤ 20 với 2ⁿ và n ≤ 10 với n!).

Đoạn code dưới đây minh họa trực tiếp số bước chạy của các mẫu vòng lặp O(log n), O(√n) và O(n log n) khi n = 1024:

#include <iostream>
using namespace std;

int main() {
    int n = 1024;

    // 1. Vòng lặp nhân đôi biến chạy -> O(log n)
    int buocLog = 0;
    for (int x = 1; x < n; x *= 2) {
        buocLog++;
    }

    // 2. Vòng lặp kiểm tra đến căn bậc hai -> O(sqrt(n))
    int buocCan = 0;
    for (int i = 1; i * i <= n; ++i) {
        buocCan++;
    }

    // 3. Vòng ngoài n lần, vòng trong nhân đôi -> O(n log n)
    int buocNLogN = 0;
    for (int i = 1; i <= n; ++i) {
        for (int x = 1; x < n; x *= 2) {
            buocNLogN++;
        }
    }

    cout << buocLog << " " << buocCan << " " << buocNLogN << "\n";  // 10 32 10240
    return 0;
}

n = 1024

# 1. Vòng lặp nhân đôi biến chạy -> O(log n)
buoc_log, x = 0, 1
while x < n:
    buoc_log += 1
    x *= 2

# 2. Vòng lặp kiểm tra đến căn bậc hai -> O(sqrt(n))
buoc_can, i = 0, 1
while i * i <= n:
    buoc_can += 1
    i += 1

# 3. Vòng ngoài n lần, vòng trong nhân đôi -> O(n log n)
buoc_nlogn = 0
for _ in range(n):
    x = 1
    while x < n:
        buoc_nlogn += 1
        x *= 2

print(buoc_log, buoc_can, buoc_nlogn)  # 10 32 10240

Bảng tra nhanh: Nhìn giới hạn N trong đề bài để chọn thuật toán

Trong hầu hết các kỳ thi lập trình và hệ thống chấm bài trực tuyến, giới hạn thời gian cho mỗi test thường là 1 giây (tương đương khoảng 10⁷ đến 10⁸ phép tính cơ bản). Vì vậy, trước khi bắt tay vào viết code, bạn hãy nhìn dòng "Giới hạn" (Constraints) của đề bài và tra bảng sau:

Độ phức tạp bộ nhớ (Space Complexity) là gì?

Bên cạnh thời gian chạy (Time Complexity), mỗi bài toán còn có giới hạn bộ nhớ (thường là 256 MB). Độ phức tạp bộ nhớ đo lượng ô nhớ phụ thêm mà thuật toán cần cấp phát theo n:

• Nếu chỉ dùng vài biến đơn lẻ (lo, hi, mid, tong): bộ nhớ phụ là O(1).
• Nếu tạo thêm một mảng phụ pref gồm n phần tử kiểu long long (mỗi phần tử 8 byte): bộ nhớ là O(n). Với n = 10^6, mảng này tốn khoảng 8 MB — rất an toàn.
• Nếu tạo một ma trận hai chiều a[10000][10000] kiểu int (4 byte): tổng số phần tử là 10⁸, ngốn khoảng 400 MB và sẽ bị báo lỗi Memory Limit Exceeded (MLE — vượt quá bộ nhớ).
• Với hàm đệ quy gọi sâu n tầng, mỗi tầng đang chờ trên ngăn xếp (call stack) cũng tiêu tốn một khung bộ nhớ, nên độ phức tạp bộ nhớ của nó là O(n) dù bạn không khai báo mảng nào.

Lỗi hay gặp khi tính độ phức tạp

Luyện ngay trên Big-O Coding

Hãy áp dụng ngay cách nhìn giới hạn n để chọn thuật toán phù hợp cho các bài tập miễn phí dưới đây:

Câu hỏi thường gặp

Nguồn tham khảo

• MIT 6.006 Lecture 1: Asymptotic Complexity
• CSES Competitive Programmer's Handbook — Chapter 2: Time Complexity
• Big-O Coding: Lộ trình Zero-100