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

Có hai thuật toán cùng giải một bài toán. Làm sao biết cái nào “tốt hơn”? Cách trực quan nhất là chạy thử cả hai và bấm giờ - nhưng cách này có hai lỗ hổng lớn.

Thứ nhất, kết quả phụ thuộc vào môi trường thực thi (nơi code được chạy): một thuật toán có thể nhanh hơn trên máy này nhưng chậm hơn trên máy khác, tùy CPU, RAM, thậm chí là những tiến trình khác đang chạy nền. Thứ hai, kết quả phụ thuộc vào dữ liệu đưa vào: thuật toán A có thể nhanh hơn B với 100 phần tử, nhưng chậm hơn hẳn khi dữ liệu tăng lên 1 triệu phần tử. Muốn có kết luận đáng tin, bạn phải test trên nhiều máy, nhiều kích thước dữ liệu - rất tốn công.

Độ phức tạp (complexity) giải quyết cả hai vấn đề trên bằng cách bỏ qua “thời gian chạy tính bằng giây” và thay vào đó đo tốc độ tăng của khối lượng công việc khi dữ liệu đầu vào lớn dần. Đây là phép đo độc lập với phần cứng, ngôn ngữ lập trình hay compiler - chỉ phụ thuộc vào chính thuật toán.

Đếm phép toán thay vì đếm giây

Thay vì đo thời gian chạy thật (phụ thuộc phần cứng), ta đếm số phép toán cơ bản (gán, so sánh, cộng trừ…) mà thuật toán thực hiện, biểu diễn dưới dạng một hàm số theo kích thước đầu vào n. Ví dụ:

def vi_du(n):
    a = 1          # 1 phép gán
    a = a + 1      # 1 phép cộng
    for i in range(n):   # lặp n lần
        print(i)          # n phép in

Đoạn code trên thực hiện khoảng 2 + n phép toán. Khi n đủ lớn, số hạng 2 (không phụ thuộc n) gần như không còn ý nghĩa gì so với n - dù n là 1 nghìn hay 1 triệu, độ chênh lệch do “cộng thêm 2” luôn không đáng kể. Đây chính là bản chất đằng sau Big O: khi kích thước đầu vào tăng lên đủ lớn, tốc độ tăng trưởng của thuật toán gần như hoàn toàn do số hạng tăng nhanh nhất trong biểu thức quyết định. Các hằng số nhân phía trước, hay những số hạng bậc thấp hơn, tuy vẫn có mặt trong công thức, nhưng ảnh hưởng của chúng trở nên không đáng kể so với số hạng chủ đạo - vì vậy ta có thể bỏ qua chúng mà không làm sai lệch bức tranh tổng thể. Nói cách khác, “hình dạng” của đường cong tăng trưởng - tức là thuật toán chạy nhanh hay chậm khi dữ liệu đầu vào ngày càng lớn - chỉ phụ thuộc vào số hạng lớn nhất đó mà thôi.

Big O Notation

Big O là ký hiệu toán học mô tả cận trên tiệm cận (asymptotic upper bound) của hàm số đếm phép toán - nói đơn giản, nó trả lời câu hỏi: “khi n tiến tới vô cực, thời gian chạy tăng theo dạng nào?”

Bốn quy tắc nhẩm nhanh

Khi đọc code và muốn suy ra Big O mà không cần tính toán chi tiết, hãy áp dụng bốn quy tắc sau.

1. Bỏ hằng số nhân. O(2n), O(3n), O(100n) đều là tuyến tính - quy về O(n). Vòng lặp chạy 2 lần liên tiếp không đổi bậc, chỉ tăng hằng số nhân.

2. Chỉ giữ số hạng lớn nhất. Với T(n) = n² + n, khi n = 1000 thì n² = 1.000.000 còn n chỉ là 1000 - số hạng n gần như vô nghĩa. Quy tắc: O(n² + n) → O(n²), O(2ⁿ + n²) → O(2ⁿ).

3. Hai đoạn code chạy tuần tự → cộng. Duyệt mảng a xong rồi duyệt mảng b (hai vòng lặp riêng biệt, không lồng nhau) tốn O(a) + O(b) = O(a + b). Chú ý: nếu a và b là hai mảng độc lập, kết quả không rút gọn thành O(n) được, vì kích thước hai mảng khác nhau.

4. Vòng lặp lồng nhau → nhân. Với mỗi phần tử của mảng a (chạy a lần), lại duyệt toàn bộ mảng b (chạy b lần) → tổng cộng O(a × b). Đây là lý do hai vòng for lồng nhau, mỗi vòng chạy n lần, cho ra O(n²).

def minh_hoa(a, b):
    for x in a:              # chạy len(a) lần
        print(x)
    for y in b:               # chạy riêng, độc lập -> CỘNG
        print(y)

    for x in a:               # chạy len(a) lần
        for y in b:            # với mỗi x, chạy hết b -> NHÂN
            print(x, y)
# Độ phức tạp: O(a + b) + O(a × b) = O(a × b) khi a, b đủ lớn

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

Xếp theo thứ tự tăng dần, đây là “thang đo” mà gần như mọi thuật toán bạn gặp đều rơi vào một trong các bậc sau:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Bậc	Tên gọi	Ý nghĩa trực quan	Ví dụ điển hình
`O(1)`	Hằng số	Không phụ thuộc `n`	Truy cập `arr[i]`, tra hash table
`O(log n)`	Logarit	Mỗi bước loại bỏ một nửa dữ liệu	Binary Search
`O(n)`	Tuyến tính	Chạm mỗi phần tử đúng 1 lần	Duyệt mảng
`O(n log n)`	Tuyến tính-logarit	`n` bước, mỗi bước tốn `log n` (hoặc ngược lại)	Merge Sort, Quick Sort
`O(n²)`	Bậc hai	Vòng lặp lồng trong vòng lặp	So sánh mọi cặp phần tử
`O(2ⁿ)`	Mũ	Mỗi phần tử nhân đôi số nhánh cần xét	Fibonacci đệ quy không nhớ
`O(n!)`	Giai thừa	Xét mọi hoán vị có thể	Sinh tất cả permutation

O(1) - hằng số

Số phép toán không đổi dù n tăng bao nhiêu. Đây là “trần” tốt nhất có thể đạt được.

def get_first(arr):
    return arr[0]          # luôn 1 bước, bất kể mảng dài bao nhiêu

O(log n) - logarit

Xuất hiện khi mỗi bước loại bỏ một nửa không gian tìm kiếm - giống cách bạn tra từ điển: mở giữa, so sánh, rồi chỉ xét nửa còn lại. Với n = 1.000.000, log₂n chỉ khoảng 20 - nghĩa là binary search trên một triệu phần tử chỉ cần tối đa 20 lần so sánh.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1   # loại bỏ nửa trái
        else:
            right = mid - 1  # loại bỏ nửa phải
    return -1

O(n) - tuyến tính

Số phép toán tỷ lệ thuận với n - mỗi phần tử được “chạm” đúng một số lần cố định.

def find_max(arr):
    max_val = arr[0]
    for num in arr:        # chạm từng phần tử 1 lần
        if num > max_val:
            max_val = num
    return max_val

O(n log n) - tuyến tính-logarit

Đặc trưng của các thuật toán sắp xếp hiệu quả (Merge Sort, Quick Sort, Heap Sort): dữ liệu được chia đôi liên tục (log n tầng chia), và ở mỗi tầng phải xử lý qua toàn bộ n phần tử.

O(n²) - bậc hai

Thường xuất hiện khi so sánh mọi cặp phần tử với nhau - vòng lặp ngoài chạy n lần, mỗi lần lại chạy một vòng lặp trong n lần.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):            # n lần
        for j in range(n - 1):    # x n lần nữa
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

O(2ⁿ) và O(n!) - mũ và giai thừa

Hai bậc này tăng cực nhanh, chỉ chấp nhận được với n rất nhỏ (thường dưới 20-30). Chúng thường xuất hiện trong đệ quy không tối ưu (ví dụ Fibonacci tính lại cùng một giá trị nhiều lần) hoặc các bài toán duyệt toàn bộ khả năng (sinh hoán vị, brute-force). Khi gặp độ phức tạp mũ, cách xử lý thường là quy hoạch động (loại bỏ tính lại) hoặc tham lam/backtracking có cắt tỉa.

Trường hợp tốt nhất, xấu nhất, trung bình

Cùng một thuật toán có thể chạy nhanh chậm khác nhau tùy dữ liệu cụ thể, không chỉ tùy kích thước n. Ví dụ tìm số 1 trong một mảng đã xáo trộn ngẫu nhiên chứa các số 1..n:

Nếu 1 nằm ngay đầu mảng, thuật toán dừng sau 1 bước → trường hợp tốt nhất (best case), ký hiệu Ω(1).
Nếu 1 nằm ở cuối mảng, thuật toán phải quét hết n phần tử → trường hợp xấu nhất (worst case), ký hiệu O(n).
Tính trung bình trên mọi vị trí có thể của 1, số bước kỳ vọng là n/2 → trường hợp trung bình (average case), ký hiệu Θ(n).

Trong thực tế, người ta gần như luôn dùng worst case (Big O) làm tiêu chuẩn, vì nó cho một “cận an toàn” - đảm bảo thuật toán không bao giờ chậm hơn mức đó, bất kể dữ liệu đầu vào là gì. Best case hiếm khi hữu ích vì nó chỉ xảy ra với xác suất rất nhỏ; average case tuy phản ánh thực tế hơn nhưng khó tính toán với thuật toán phức tạp.

Tóm tắt

Độ phức tạp đo xu hướng tăng của khối lượng công việc theo kích thước dữ liệu, không đo thời gian chạy thực tế - nhờ vậy kết quả không phụ thuộc phần cứng hay ngôn ngữ lập trình.
Big O mô tả cận trên tiệm cận; khi nhẩm nhanh, hãy bỏ hằng số, chỉ giữ số hạng lớn nhất, cộng cho các đoạn code tuần tự và nhân cho vòng lặp lồng nhau.
Thang đo phổ biến: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
Trong thực hành, Big O thường ngầm hiểu là worst case - cận an toàn cho hiệu năng thuật toán.