Các Thuật Toán Hoàn Thành Đúng Thời Gian: Kiểm Tra Độ Phức Tạp Trực Giác

Bạn viết một hàm, chạy nó trên dữ liệu kiểm tra của mình, và nó hoạt động tốt. Sau đó nó được chuyển sang dữ liệu production — 500,000 hàng thay vì 500 — và request hết timeout. Điều này xảy ra liên tục, và hầu như luôn là một vấn đề độ phức tạp ẩn sau mã vẻ hợp lý ở quy mô nhỏ.

Tại sao laptop của bạn đã dối bạn

Một thuật toán O(n²) chạy trên 100 item thực hiện 10,000 phép toán. Điều đó tức thì trên bất kỳ máy nào. Chạy cùng một thuật toán trên 100,000 item và bạn ở mức 10 tỷ phép toán — phút hoặc giờ thay vì mili giây. Bước nhảy từ n sang n² không cảm thấy nguy hiểm cho đến khi n trở nên lớn, đó chính xác là lý do tại sao nó qua mặt review code và kiểm tra cục bộ.

Một ví dụ cổ điển: kiểm tra duplicates bằng vòng lặp lồng nhau.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Đây là O(n²). Thay bằng một set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Bây giờ nó là O(n). Việc tra cứu set là trung bình O(1), nên toàn bộ hàm tỷ lệ tuyến tính thay vì bình phương. Trên 10,000 item đó là sự khác biệt giữa khoảng 100 triệu so sánh và 10,000.

Đo lường trước khi tối ưu hóa

Đừng đoán. Sử dụng timeit cho microbenchmarks:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Cho các hàm lớn hơn, hãy profile bằng cProfile:

python -m cProfile -s cumulative myscript.py

Nhìn vào cột cumtime. Nếu một hàm chiếm 90% thời gian chạy, đó là mục tiêu của bạn. Tối ưu hóa code không phải là nút thắt lãng phí thời gian của bạn và thêm độ phức tạp mà không có lợi ích.

Các mẫu phổ biến im lặng trở nên chậm

Kiểm tra thành viên list lặp lại. if x in my_list là O(n) cho một list nhưng O(1) trung bình cho một set hoặc dict. Nếu bạn kiểm tra thành viên bên trong một vòng lặp, kiểm tra O(n) đó bên trong vòng lặp O(n) cho bạn O(n²) tổng thể. Thay list bằng set và bạn quay trở lại O(n).

Nối chuỗi trong một vòng lặp. Trong Python, result += chunk bên trong một vòng lặp trên các chuỗi là O(n²) trong trường hợp xấu nhất vì chuỗi không thay đổi được và mỗi nối sao chép toàn bộ thứ. Hãy sử dụng ''.join(chunks) thay thế — nó xây dựng chuỗi một lần.

Sắp xếp khi bạn không cần thiết. sorted() là O(n log n). Nếu bạn gọi nó bên trong một vòng lặp chỉ để tìm max hoặc min mỗi lần lặp, hãy sử dụng max()/min() (O(n)) hoặc tốt hơn, một heap (heapq) nếu bạn cần cực trị chạy nhiều lần. heapq.nlargest(k, data) là O(n log k), rẻ hơn nhiều so với sắp xếp toàn bộ list khi k nhỏ.

Các hàm đệ quy mà không ghi nhớ. Fibonacci đệ quy ngây thơ là O(2ⁿ) vì nó tính toán lại các bài toán con giống nhau liên tục. Thêm functools.lru_cache và nó giảm xuống O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Đọc Big O từ code thực tế, nhanh

Đếm vòng lặp lồng nhau trên cùng một input — đó thường là số mũ của bạn. Một vòng lặp duy nhất là O(n). Một vòng lặp bên trong một vòng lặp là O(n²) trừ khi phạm vi vòng lặp bên trong co lại (như trong hình thức tối ưu hóa của bubble sort, vẫn O(n²) trường hợp xấu nhất nhưng ít so sánh hơn). Các cuộc gọi đệ quy chia vấn đề thành hai nửa, giống như binary search hoặc merge sort, chỉ đến O(log n) hoặc O(n log n). Các cuộc gọi đệ quy chia nhánh thành nhiều cuộc gọi cho mỗi cấp, giống như Fibonacci ngây thơ, chỉ đến thời gian hàm mũ — một tín hiệu mạnh mẽ rằng bạn cần ghi nhớ hoặc viết lại lặp lại.

Một thói quen tốt: trước khi bạn viết vòng lặp lồng nhau hoặc đệ quy quy trên dữ liệu hướng người dùng, hãy hỏi n có thể thực tế là bao nhiêu trong production, không phải trong tệp kiểm tra của bạn. Nếu n có thể đạt sáu chữ số, một giải pháp O(n²) cần kiểm tra kỹ trước khi nó được triển khai.

Để biết thêm về phân tích độ phức tạp, thuật toán sắp xếp và các công cụ profiling, hãy xem các phần Python và Computer Science trên Korra Studio.