Độ phức tạp thời gian (Big-O)

huunguyen · Last updated 28, Tháng 3, 2026, 22:43

Độ phức tạp thời gian mô tả tốc độ tăng của thời gian chạy khi kích thước đầu vào $N$ tăng lên. Đây là công cụ để đánh giá xem một thuật toán có đủ nhanh cho một bài toán hay không.

Ký hiệu Big-O

Big-O ( $O$ ) mô tả cận trên của thời gian chạy trong trường hợp xấu nhất. Ta bỏ qua hằng số và các số hạng bậc thấp.

Ví dụ: $3 N^{2} + 5 N + 10 = O (N^{2})$

Các độ phức tạp thường gặp

Ký hiệu	Tên	Ví dụ
$O (1)$	Hằng số	Truy cập phần tử mảng
$O (\log N)$	Logarithm	Tìm kiếm nhị phân
$O (\sqrt{N})$	Căn bậc hai	Kiểm tra số nguyên tố
$O (N)$	Tuyến tính	Duyệt mảng một lần
$O (N \log N)$	Tuyến tính-log	Merge sort, Heap sort
$O (N^{2})$	Bậc hai	Bubble sort, vòng lặp lồng nhau
$O (N^{3})$	Bậc ba	Floyd-Warshall
$O (2^{N})$	Hàm mũ	Duyệt tất cả tập con
$O (N!)$	Giai thừa	Duyệt hoán vị

Cách tính độ phức tạp

Vòng lặp đơn — $O (N)$

for (int i = 0; i < n; i++) {
    // O(1) mỗi lần lặp
}
// Tổng: O(N)

Vòng lặp lồng nhau — $O (N^{2})$

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // O(1) mỗi lần lặp
    }
}
// Tổng: O(N^2)

Chia đôi mỗi bước — $O (\log N)$

int x = n;
while (x > 1) {
    x /= 2;
}
// Tổng: O(log N)

Hai đoạn độc lập — $O (N + M)$

for (int i = 0; i < n; i++) { ... }  // O(N)
for (int j = 0; j < m; j++) { ... }  // O(M)
// Tổng: O(N + M)

Thứ tự tăng dần

O (1) < O (\log N) < O (\sqrt{N}) < O (N) < O (N \log N) < O (N^{2}) < O (N^{3}) < O (2^{N}) < O (N!)

Ví dụ thực tế

Bài toán: Kiểm tra xem mảng có hai phần tử bằng nhau không.

// Cách 1: O(N^2) — vòng lặp lồng nhau
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        if (a[i] == a[j]) return true;

// Cách 2: O(N log N) — sắp xếp rồi kiểm tra kề nhau
sort(a, a+n);
for (int i = 0; i+1 < n; i++)
    if (a[i] == a[i+1]) return true;

// Cách 3: O(N) — dùng hash set
unordered_set<int> seen;
for (int x : a)
    if (!seen.insert(x).second) return true;

Bình luận

Không có bình luận tại thời điểm này.