Ký hiệu Big O (độ phức tạp thuật toán) giải thích qua ví dụ

Big O giải quyết vấn đề gì

Đo chương trình bằng giây chỉ cho bạn biết về một máy, một ngôn ngữ và một bộ dữ liệu. Big O trả lời câu hỏi hữu ích hơn: nếu đầu vào lớn gấp 10 lần thì thuật toán phải làm thêm bao nhiêu việc? Thuật toán làm nhiều gấp 10 lần mở rộng khác hẳn thuật toán làm nhiều gấp 100 lần.

Theo định nghĩa hình thức, f(n) là O(g(n)) nếu tồn tại các hằng số c và n₀ sao cho f(n) ≤ c · g(n) với mọi n ≥ n₀. Nói đơn giản, g là cận trên cho tốc độ tăng của f khi n đủ lớn, bỏ qua các hệ số hằng.

• n là kích thước đầu vào: độ dài danh sách, số ký tự của chuỗi, số nút của đồ thị.
• Độ phức tạp thời gian đếm số bước cơ bản (so sánh, gán, phép tính số học).
• Độ phức tạp không gian đếm lượng bộ nhớ phụ sử dụng, không tính bản thân đầu vào.

Cách rút gọn một biểu thức

Đếm số bước dưới dạng hàm của n, rồi áp dụng hai quy tắc: bỏ hệ số hằng và chỉ giữ số hạng trội nhất.

Khi thuật toán có hai đầu vào độc lập, hãy giữ cả hai: duyệt danh sách độ dài n rồi duyệt danh sách độ dài m là O(n + m), còn vòng lặp lồng trong vòng lặp là O(n · m). Cơ số của logarit không quan trọng trong Big O, vì log₂ n và log₁₀ n chỉ khác nhau một hệ số hằng.

Các lớp độ phức tạp phổ biến

Ước lượng thô: trên máy tính hiện đại, một vòng lặp đơn giản trong Python chạy được vài chục triệu bước cơ bản mỗi giây, còn ngôn ngữ biên dịch nhanh hơn nhiều. Vì vậy O(n log n) vẫn ổn với hàng triệu phần tử, O(n²) bắt đầu chậm ở mức vài chục nghìn, còn O(2ⁿ) vô vọng khi vượt quá khoảng 40 đến 60 phần tử.

Đọc độ phức tạp từ mã Python

Hãy nhìn vào các vòng lặp. Một vòng lặp duyệt đầu vào là O(n). Vòng lặp lồng trong một vòng lặp khác trên cùng đầu vào là O(n²). Vòng lặp mỗi lần giảm một nửa phạm vi còn lại là O(log n).

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

Các lệnh gọi thư viện cũng có chi phí riêng. x in some_list là O(n), x in some_set trung bình là O(1), list.insert(0, x) là O(n) vì mọi phần tử phải dịch chuyển, còn sorted() là O(n log n). Vòng lặp gọi một thao tác O(n) tổng cộng n lần là O(n²), dù trông như chỉ có một vòng lặp.

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

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

Cùng một thuật toán có thể làm lượng việc khác nhau trên các đầu vào cùng kích thước, nên độ phức tạp thường được nêu cho ba trường hợp.

Khi người ta chỉ nói “độ phức tạp của X”, thường họ muốn nói trường hợp xấu nhất, hoặc trường hợp trung bình với bảng băm và sắp xếp nhanh. Chi phí khấu hao là ý thứ tư: thêm phần tử vào cuối list của Python đôi khi là O(n) khi list phải mở rộng vùng lưu trữ, nhưng trung bình qua nhiều lần thêm thì là O(1).

Big O, Big Omega và Big Theta

Nói chặt chẽ, thuật toán O(n) cũng là O(n²), vì O chỉ là cận trên. Trong thực tế, mọi người viết Big O nhưng ngụ ý cận chặt nhất mà họ biết, đó chính là điều Θ biểu diễn.

Lỗi thường gặp

• Quên chi phí của các thao tác có sẵn, như in trên list hay cắt lát items[1:], vốn sao chép dữ liệu và tốn O(k) cho k phần tử được sao chép.
• Đếm sai số lần gọi đệ quy: hàm tự gọi hai lần với n − 1 là O(2ⁿ), không phải O(n).
• Bỏ qua không gian: tạo list mới kích thước n, hoặc đệ quy sâu n tầng, tốn O(n) bộ nhớ.
• Viết O(2n) hoặc O(n + 5). Cả hai đều rút gọn thành O(n).