Thuật toán 1 — Độ phức tạp & tư duy Big-O

Vì sao phải quan tâm độ phức tạp?

Có một sự thật cay đắng mà hầu như ai làm dữ liệu cũng gặp ít nhất một lần: một đoạn code chạy ngon lành trên bộ dữ liệu thử nghiệm 1.000 dòng, đến khi bung ra 10 triệu dòng thì "chết" đứng — không phải chạy chậm, mà là chạy tới sáng vẫn chưa xong, hoặc tràn bộ nhớ rồi bị hệ điều hành giết. Điều đáng nói là nó không "hỏng" — nó chạy đúng, chỉ là chạy quá lâu. Và bạn không thể mua thêm CPU để cứu được, vì vấn đề nằm ở bản chất của thuật toán, không phải ở phần cứng.

Độ phức tạp (complexity) chính là công cụ để bạn dự đoán trước điều đó, ngay khi còn đang viết code, trước khi dữ liệu thật kịp trừng phạt bạn. Nó trả lời câu hỏi: "Nếu dữ liệu lớn gấp 10 lần, thời gian chạy tăng gấp mấy?" Với một thuật toán, câu trả lời là "gấp 10". Với một thuật toán khác, câu trả lời là "gấp 100". Với thuật toán tệ nhất, câu trả lời là "gấp 3,6 triệu lần" (đó là 10! chia 1!, và bạn sẽ hiểu vì sao ở phần dưới).

Đây là tư duy scale — cùng một dòng chảy với data engineering: khi thiết kế pipeline xử lý bảng giao dịch, câu hỏi không phải "có chạy được không" mà "chạy được ở quy mô nào, và khi quy mô tăng thì sao". Bài này là nền tảng cho cả loạt: hiểu độ phức tạp rồi bạn mới biết vì sao nên chọn set thay list, vì sao sort tốt là O(n log n), và vì sao đối soát hai bảng bằng vòng lặp lồng là tự sát.

1. Big-O là gì — và nó KHÔNG đo cái gì

Big-O mô tả tốc độ tăng của chi phí (thời gian hoặc bộ nhớ) theo kích thước đầu vào n, khi n tiến ra lớn. Điểm cốt lõi: nó quan tâm hình dạng của đường cong, không quan tâm con số tuyệt đối.

Vì vậy Big-O làm hai việc "thô bạo" mà người mới hay sốc:

• Bỏ hằng số nhân. 5n và 100n đều là O(n). Một thuật toán chậm gấp 20 lần vẫn cùng lớp độ phức tạp — vì khi n đủ lớn, cả hai đều tăng tuyến tính.
• Bỏ các bậc thấp hơn. n² + 1000n + 50000 là O(n²). Khi n = 1.000.000, số hạng n² lớn gấp cả triệu lần phần còn lại; những số hạng kia trở thành hạt bụi.

Tại sao "thô bạo" như vậy lại hữu ích? Vì mục tiêu là so sánh bản chất, không phải benchmark chính xác. Big-O nói cho bạn biết đường cong nào rồi cũng vượt lên trên, bất kể hằng số. Một thuật toán O(n log n) với hằng số xấu vẫn sẽ đánh bại O(n²) khi n đủ lớn — chỉ là vấn đề thời gian.

Theo quy ước, khi nói Big-O người ta thường ngầm hiểu trường hợp xấu nhất (worst case) — cận trên của chi phí. Đây là góc nhìn phòng thủ: đảm bảo "dù xui đến mấy cũng không tệ hơn thế này".

Có hai họ hàng của Big-O bạn nên biết tên (để không bỡ ngỡ khi đọc tài liệu), dù thực chiến ít dùng:

• Big-Omega (Ω) — cận dưới, mô tả trường hợp tốt nhất.
• Big-Theta (Θ) — khi cận trên và cận dưới trùng lớp, tức thuật toán luôn tăng đúng theo tốc độ đó. Ví dụ, duyệt hết một mảng luôn là Θ(n).

Trong công việc hàng ngày, nói "Big-O" là đủ. Chỉ cần nhớ: nó là thước đo tốc độ tăng, không phải đồng hồ bấm giây.

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

Dưới đây là những lớp bạn sẽ gặp 99% thời gian, xếp từ tốt đến thảm hoạ. Với mỗi lớp có một trực giác và một ví dụ quen thuộc.

Trực giác cho từng lớp:

• O(1) — chi phí cố định. Dù dict có 10 hay 10 triệu khoá, tra một khoá vẫn mất ngần ấy thời gian (trung bình). Đây là "phép màu" của bảng băm mà ta sẽ khai thác triệt để.
• O(log n) — mỗi bước loại bỏ một nửa số ứng viên còn lại. Với 1 triệu phần tử, binary search chỉ cần ~20 bước (vì 2^20 ≈ 1 triệu). Cực nhanh, nhưng đòi hỏi dữ liệu đã sắp xếp.
• O(n) — công bằng và dễ đoán: dữ liệu gấp đôi thì thời gian gấp đôi. Phần lớn công việc "quét một lượt" nằm ở đây.
• O(n log n) — trần lý thuyết của mọi thuật toán sắp xếp dựa trên so sánh. Chậm hơn O(n) một chút nhưng vẫn rất khả thi ở quy mô lớn.
• O(n²) — kẻ thù thầm lặng. Với 1.000 phần tử là 1 triệu phép tính (chấp nhận được). Với 1 triệu phần tử là 1.000 tỷ phép tính — bạn sẽ chờ tới mùa quýt.
• O(2^n) và O(n!) — vùng cấm. Chúng chỉ khả thi với n cực nhỏ (dưới ~20-25). Đây là lý do các bài toán tối ưu tổ hợp cần thuật toán thông minh (quy hoạch động, heuristic) chứ không thể brute-force.

Để thấy sự chênh lệch tàn khốc, giả sử máy làm được 1 tỷ phép tính/giây và n = 1.000.000:

Nhìn dòng O(n²): cùng dữ liệu 1 triệu bản ghi, thứ chạy trong mili-giây với O(n) thì chạy hơn 11 ngày với O(n²). Đây không phải khác biệt định lượng, mà là khác biệt giữa làm được và bất khả thi.

Sơ đồ dưới cho thấy hình dạng đường cong khi n tăng — vì sao các lớp cao "bốc" lên thẳng đứng:

3. Độ phức tạp không gian & đánh đổi thời gian ↔ bộ nhớ

Big-O không chỉ đo thời gian. Độ phức tạp không gian (space complexity) đo lượng bộ nhớ thêm mà thuật toán cần, cũng theo n. Thuật toán chỉ dùng vài biến là O(1) không gian; thuật toán tạo một bản sao của toàn bộ dữ liệu là O(n).

Điều thú vị là hai loại độ phức tạp này thường đánh đổi lẫn nhau. Kinh điển nhất: caching / precompute — dùng thêm bộ nhớ để đổi lấy thời gian. Ví dụ ở phần đối soát bên dưới, ta sẽ xây một set (tốn O(n) bộ nhớ) để biến việc tra cứu từ O(n) xuống O(1). Đó là đánh đổi rất đáng: hy sinh một chút RAM để cắt thời gian từ hàng ngày xuống hàng giây.

Chiều ngược lại cũng có: nếu bộ nhớ eo hẹp (dữ liệu lớn hơn RAM), bạn có thể chấp nhận thuật toán chậm hơn nhưng chỉ đọc dữ liệu theo luồng (streaming), giữ không gian ở mức O(1) thay vì nạp tất cả vào bộ nhớ. Data engineering đầy những đánh đổi kiểu này — xem loạt bài về xử lý dữ liệu lớn.

4. Amortized và trung bình vs xấu nhất

Đây là chỗ nhiều người hiểu sai, dẫn tới đánh giá thuật toán quá bi quan.

Trung bình vs xấu nhất — bảng băm (dict/set). Tra một khoá trong dict Python trung bình là O(1). Nhưng về mặt lý thuyết, xấu nhất là O(n) — điều xảy ra khi mọi khoá "băm" vào cùng một chỗ (đụng độ hàng loạt). Trong thực tế với dữ liệu bình thường, điều này gần như không bao giờ xảy ra, nên ta cứ tự tin coi tra cứu dict/set là O(1). Việc phân biệt trung bình vs xấu nhất giúp bạn hiểu rủi ro tiềm ẩn, nhưng không nên vì cái xấu nhất hiếm hoi mà từ chối một cấu trúc tuyệt vời.

Amortized (chi phí bình quân theo chuỗi thao tác) — list.append. Đây là khái niệm tinh tế hơn. Khi bạn append vào một list Python, hầu hết lần là O(1). Nhưng thi thoảng list đầy chỗ, nó phải cấp phát vùng nhớ lớn hơn và sao chép toàn bộ phần tử cũ sang — lần đó tốn O(n).

Nghe có vẻ tệ, nhưng mẹo nằm ở chỗ: list không tăng thêm 1 ô mỗi lần, mà tăng theo tỷ lệ (nhân đôi hoặc gần vậy). Vì lần sao chép đắt đỏ xảy ra càng lúc càng thưa, chi phí đắt đó được "trải đều" (amortize) ra vô số lần append rẻ. Kết quả: chèn n phần tử tổng cộng chỉ tốn O(n), tức mỗi lần append là O(1) amortized.

Điểm khác biệt then chốt cần nhớ:

• Average case nói về phân phối dữ liệu đầu vào (giả định input "điển hình").
• Amortized nói về phân phối chi phí qua một chuỗi thao tác — không phụ thuộc may rủi của input, mà là bảo đảm toán học rằng tổng chi phí của cả chuỗi bị chặn.

Bảng băm khi phải rehash (mở rộng bảng) cũng amortized O(1) theo đúng logic này: lần mở rộng tốn O(n) nhưng thưa dần, trải đều ra thì mỗi lần chèn vẫn là O(1) bình quân.

5. Ước lượng độ phức tạp trong thực tế

Không cần lý thuyết cao siêu, chỉ cần vài quy tắc đếm:

1. Vòng lặp chạy qua n phần tử → O(n).
2. Vòng lặp lồng trong vòng lặp → nhân lên. Hai vòng lặp n lồng nhau là O(n²); ba vòng là O(n³).
3. Chia đôi mỗi bước → O(log n). Nếu thấy n = n // 2 hay tương tự trong điều kiện lặp, nghĩ ngay tới logarit.
4. Các bước nối tiếp (không lồng) → lấy lớp cao nhất. Một vòng O(n) rồi một vòng O(n²) thì tổng là O(n²).

Nhưng cái bẫy lớn nhất là chi phí ẩn của từng thao tác. Một dòng code trông "một phép" chưa chắc là O(1):

• x in my_list — kiểm tra phần tử trong list là O(n) (phải quét). Cùng cú pháp nhưng x in my_set là O(1). Đây là khác biệt sống còn — chi tiết ở bài Cấu trúc dữ liệu.
• my_list.insert(0, x) — chèn đầu list là O(n) vì phải dời mọi phần tử.
• Sao chép (list(x), x[:], copy.deepcopy) — O(n) hoặc hơn, dễ bị quên khi nằm trong vòng lặp.
• In ra màn hình (print) trong vòng lặp lớn — I/O chậm, có thể lấn át cả thời gian tính.

Vì vậy, muốn đánh giá đúng, phải biết chi phí thao tác của từng cấu trúc (list vs set vs dict) — nội dung cốt lõi của bài tiếp theo.

6. Ví dụ minh hoạ

6.1. Đối soát cặp: O(n²) vs dùng set O(n)

Bài toán: cho hai danh sách mã giao dịch, tìm những mã có ở cả hai.

# (minh hoạ)
# CÁCH TỆ — O(n * m): với mỗi phần tử của danh sách A, quét toàn bộ B
def khop_cham(a: list[str], b: list[str]) -> list[str]:
    ket_qua = []
    for ma in a:            # n lần
        if ma in b:         # 'in' trên list = O(m) mỗi lần
            ket_qua.append(ma)
    return ket_qua          # tổng: O(n * m) ~ O(n²)


# CÁCH TỐT — O(n + m): đổ B vào set rồi tra cứu O(1)
def khop_nhanh(a: list[str], b: list[str]) -> list[str]:
    b_set = set(b)          # xây set: O(m), tốn O(m) bộ nhớ
    return [ma for ma in a if ma in b_set]   # mỗi 'in' set = O(1)

Hai hàm cho cùng kết quả, nhưng bản khop_nhanh đổi một chút bộ nhớ (set) lấy tốc độ khủng khiếp. Đây chính là đánh đổi thời gian ↔ không gian đã nói ở mục 3.

6.2. Binary search: O(log n) — sức mạnh của cắt đôi

# (minh hoạ)
def binary_search(arr: list[int], target: int) -> int:
    """Trả về chỉ số của target trong mảng ĐÃ SẮP XẾP, hoặc -1. O(log n)."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2      # xét phần tử giữa
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1          # loại bỏ nửa trái
        else:
            hi = mid - 1          # loại bỏ nửa phải
    return -1

Mỗi vòng lặp vứt đi một nửa số ứng viên. Với mảng 1 triệu phần tử, tối đa ~20 vòng là xong — so với quét tuyến tính có thể mất tới 1 triệu bước. Cái giá phải trả: mảng phải được sắp xếp trước (xem bài Sorting & searching).

7. Đo bằng thực nghiệm — lý thuyết cần kiểm chứng

Big-O cho bạn bản chất, nhưng hằng số ẩn và đặc thù máy chỉ đo mới biết. Công cụ chuẩn trong Python là timeit:

# (minh hoạ)
import timeit

setup = """
import random
a = [str(i) for i in range(50_000)]
b = [str(random.randint(0, 100_000)) for _ in range(50_000)]
"""

t_cham = timeit.timeit("[x for x in a if x in b]", setup=setup, number=3)
t_nhanh = timeit.timeit(
    "s = set(b); [x for x in a if x in s]", setup=setup, number=3
)
print(f"O(n^2): {t_cham:.3f}s | O(n): {t_nhanh:.3f}s")

Chạy thử với n tăng dần (10k, 20k, 40k) và quan sát: nếu tăng gấp đôi n mà thời gian tăng gấp 4, bạn đang ở O(n²); nếu tăng gần gấp đôi, đó là O(n). Đường cong thời gian thực nghiệm là bằng chứng cho lớp độ phức tạp lý thuyết.

Quan trọng: đo trên dữ liệu đủ lớn — với n nhỏ, hằng số và nhiễu lấn át, bản "tệ" có khi lại nhanh hơn. Chi tiết về profiling, benchmark và tối ưu hiệu năng nằm ở bài Đồng thời, song song & hiệu năng.

8. Use case thực tế: đối soát hai danh sách 1 triệu bản ghi

Tình huống ngân hàng rất quen: cuối ngày cần đối soát giao dịch giữa hệ thống nội bộ và file từ đối tác/cổng thanh toán — mỗi bên ~1 triệu bản ghi, cần tìm giao dịch lệch (có ở bên này mà thiếu bên kia).

Cách ngây thơ — vòng lặp lồng, O(n²): với mỗi giao dịch trong danh sách A, quét toàn bộ danh sách B để tìm. Số phép so sánh: 1.000.000 × 1.000.000 = 10¹² (một nghìn tỷ). Như bảng ở mục 2, với tốc độ 1 tỷ phép/giây, đó là ~11,5 ngày. Job đối soát cuối ngày mà chạy 11 ngày thì coi như hệ thống sập.

Cách dùng hash, O(n): đổ toàn bộ mã giao dịch của B vào một set (hoặc dict nếu cần kèm dữ liệu). Xây set tốn O(n); sau đó với mỗi giao dịch của A, tra cứu trong set là O(1). Tổng: O(n + m) ≈ 2 triệu thao tác — dưới một giây.

# (minh hoạ)
def doi_soat(noi_bo: list[str], doi_tac: list[str]) -> dict:
    set_noi_bo = set(noi_bo)          # O(n)
    set_doi_tac = set(doi_tac)        # O(m)
    return {
        "thieu_o_doi_tac": set_noi_bo - set_doi_tac,   # có nội bộ, thiếu đối tác
        "thieu_o_noi_bo": set_doi_tac - set_noi_bo,    # ngược lại
        "khop": set_noi_bo & set_doi_tac,              # giao — khớp cả hai
    }

Chênh lệch không phải "nhanh hơn vài lần" mà là từ bất khả thi (11 ngày) thành tầm thường (dưới 1 giây) — chỉ nhờ chọn đúng độ phức tạp. Đây cũng là hình mẫu để tránh cạm bẫy N+1 (lặp gọi tra cứu lẻ trong vòng lặp thay vì nạp một lần rồi tra tại chỗ). Các mẫu đối soát, gộp, khử trùng lặp ở quy mô lớn được đào sâu ở bài Thuật toán thực chiến với dữ liệu.

9. Cạm bẫy & Ghi nhớ

Cạm bẫy — tối ưu sớm (premature optimization). Đừng vặn vẹo từng dòng để tiết kiệm mili-giây trên đoạn code chạy một lần với 100 dòng dữ liệu. Code rối rắm khó bảo trì mà chẳng nhanh hơn thấy được. Nguyên tắc: viết cho rõ trước, đo, rồi mới tối ưu chỗ thật sự là nút thắt.

Nhưng — mặt kia của tấm huy chương: tối ưu sớm sai lầm ở hằng số, còn chọn sai lớp độ phức tạp là sai lầm cấu trúc — không phần cứng nào cứu nổi. Nếu bạn chọn O(n²) cho 10 triệu bản ghi, mua CPU nhanh gấp đôi cũng chỉ giảm từ "chết" xuống "vẫn chết". Vì vậy hai điều này không mâu thuẫn: đừng vi chỉnh sớm, nhưng phải chọn đúng lớp độ phức tạp ngay từ khâu thiết kế.

Ghi nhớ:

• Big-O đo tốc độ tăng theo n (worst case), bỏ hằng số & bậc thấp — nó nói hình dạng đường cong, không nói giây đồng hồ.
• Thuộc lòng thứ tự: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!).
• dict/set tra cứu O(1) trung bình — vũ khí số một để hạ O(n²) xuống O(n).
• list.append là O(1) amortized; x in list là O(n), x in set là O(1) — đừng nhầm.
• Đánh đổi thời gian ↔ bộ nhớ: caching/precompute (dựng set) đổi RAM lấy tốc độ.
• Cảnh giác chi phí ẩn: in list, insert(0,...), copy, print trong vòng lặp.
• Đo để kiểm chứng lý thuyết (timeit), trên dữ liệu đủ lớn.
• Khi dữ liệu lớn, chọn sai độ phức tạp = bất khả thi; hãy quyết định lớp độ phức tạp ngay từ khi thiết kế.

Bài tiếp theo: Cấu trúc dữ liệu — chi phí thao tác của list, set, dict, deque và khi nào dùng cái nào; rồi Sorting & searching và Thuật toán thực chiến với dữ liệu.