Độ phức tạp thuật toán

Tại sao cần đánh giá độ phức tạp?

Khi giải một bài thi, có nhiều cách tiếp cận khác nhau. Độ phức tạp thuật toán giúp đánh giá khả năng chạy của một lời giải trước khi cài đặt — tránh mất thời gian viết code rồi bị Time Limit Exceeded (TLE).

Có hai loại độ phức tạp cần quan tâm:

Độ phức tạp thời gian — số thao tác cần thực hiện.
Độ phức tạp không gian — lượng bộ nhớ cần dùng.

Ký hiệu Big-O

Big-O mô tả tốc độ tăng của số thao tác khi kích thước đầu vào n tăng lên. Chỉ giữ lại thành phần tăng nhanh nhất và bỏ hằng số.

Big-O	Tên gọi	Ví dụ điển hình
O(1)	Hằng số	Truy cập phần tử theo chỉ số
O(log n)	Logarithm	Tìm kiếm nhị phân
O(n)	Tuyến tính	Duyệt một mảng
O(n log n)	Log tuyến tính	Sắp xếp trộn, sắp xếp nhanh
O(n²)	Bậc hai	Sắp xếp nổi bọt, hai vòng lặp lồng nhau
O(2ⁿ)	Hàm mũ	Duyệt tất cả tập con
O(n!)	Giai thừa	Duyệt tất cả hoán vị

Ước lượng nhanh trong thi đấu

Máy tính thông thường thực hiện khoảng 10⁸ thao tác đơn giản mỗi giây. Dùng quy tắc này để ước tính:

n	O(n)	O(n log n)	O(n²)	O(2ⁿ)
10⁶	✅ ~0.01s	✅ ~0.02s	❌ ~10s	❌
10⁵	✅	✅	❌ ~100ms	❌
10⁴	✅	✅	✅ ~1ms	❌
1000	✅	✅	✅	❌
20	✅	✅	✅	✅ ~1s

Mẹo: Nhìn vào giới hạn n của bài để chọn thuật toán phù hợp.

Biểu đồ so sánh tốc độ tăng

graph LR; A[O de-1] --> B[O log-n]; B --> C[O n]; C --> D[O n-log-n]; D --> E[O n-sq]; E --> F[O 2-n]; F --> G[O n-fact]; style A fill:#198754,color:#fff style B fill:#198754,color:#fff style C fill:#0d6efd,color:#fff style D fill:#0d6efd,color:#fff style E fill:#ffc107,color:#000 style F fill:#dc3545,color:#fff style G fill:#dc3545,color:#fff

Ví dụ thực tế

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

def tinh_tong(arr):
    tong = 0
    for x in arr:   # n lần lặp
        tong += x
    return tong

# n = 10⁶ vẫn chạy nhanh

Hai vòng lặp lồng nhau — O(n²)

def tim_cap_tong(arr, target):
    n = len(arr)
    for i in range(n):          # n lần
        for j in range(i + 1, n):   # ~n lần
            if arr[i] + arr[j] == target:
                return (arr[i], arr[j])
    return None

# n = 10⁵: ~10¹⁰ thao tác → TLE
# Dùng bài này để thấy tại sao cần kỹ thuật tốt hơn

Đệ quy nhị phân — O(log n)

def dem_buoc_nhi_phan(n):
    buoc = 0
    while n > 1:
        n //= 2     # Mỗi bước chia đôi n
        buoc += 1
    return buoc

print(dem_buoc_nhi_phan(1024))  # 10 (vì 2^10 = 1024)
print(dem_buoc_nhi_phan(10**6)) # 19 (vì 2^19 ≈ 10^6)

Phân tích độ phức tạp không gian

Độ phức tạp không gian tính lượng bộ nhớ phụ cần dùng (không tính đầu vào).

# O(1) không gian — dùng cố định vài biến
def tim_max(arr):
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val

# O(n) không gian — tạo mảng phụ cùng kích thước
def nhan_doi(arr):
    return [x * 2 for x in arr]  # Tạo n phần tử mới

# O(n) không gian đệ quy — stack đệ quy sâu n cấp
def dem_nguoc(n):
    if n == 0:
        return
    print(n)
    dem_nguoc(n - 1)             # Đệ quy sâu n cấp

Kết luận

Trước khi viết code cho bất kỳ bài nào, hãy hỏi: “Thuật toán của mình có độ phức tạp bao nhiêu? Có đủ nhanh với giới hạn n không?”. Thói quen này sẽ giúp tiết kiệm rất nhiều thời gian trong thi đấu.

Trong series này: