Cách Cấu Trúc Mã Tiết Lộ Độ Phức Tạp

Cách Xác Định Big O Từ Mã

Big O ẩn trong hình dạng của mã của bạn. Bốn mẫu bao gồm hầu hết các trường hợp:

Một vòng lặp trên N phần tử: O(N)

# O(N): một lần qua danh sách
for item in list_of_n_items:
    process(item)

Vòng lặp lồng nhau, mỗi cái trên N phần tử: O(N²)

# O(N²): mỗi phần tử ghép với mỗi phần tử khác
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

Tìm kiếm thời gian hằng số: O(1)

Truy cập chỉ số mảng, tìm kiếm bảng băm — một bước bất kể kích thước.

Chia để trị (cắt vấn đề làm đôi mỗi bước): O(log N)

Tìm kiếm nhị phân: mỗi kiểm tra giảm một nửa phần tử còn lại.

---

Big O(N²) ẩn: một danh sách bên trong vòng lặp

# Cái này trông giống O(N) nhưng thực tế là O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # quét toàn bộ visited: O(N)
        visited.append(item)  # toàn bộ vòng lặp: O(N²)

Dòng if item not in visited quét từng phần tử của visited mỗi lần lặp. Quét danh sách tốn O(N). Một vòng lặp chạy N lần, mỗi lần thực hiện O(N) công việc: O(N) × O(N) = O(N²).

Mẫu này xuất hiện trong 1.000+ dự án mã nguồn mở. Sửa chữa chỉ cần một ký tự: thay thế visited = [] bằng visited = set(). Kiểm tra thành viên tập hợp tốn O(1), không phải O(N). Một thay đổi. Kết quả giống nhau. 1.000 lần nhanh hơn ở N=1.000.

Phân Loại & Sửa Chữa Mã Này

Đọc mã này:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

Lý Thuyết Gặp Thực Hành

Big O Trong Tự Nhiên

Big O không chỉ là lý thuyết. Nó phân biệt các chương trình kết thúc trong vài giây với các chương trình mất 17 phút — trên cùng một tác vụ.

Ví dụ thực tế: phát hiện chu kỳ phụ thuộc trong hệ thống xây dựng.

Khi bạn cài đặt phần mềm, máy tính của bạn giải quyết một đồ thị phụ thuộc: gói A cần B, B cần C, v.v. Một hệ thống xây dựng kiểm tra đồ thị này cho các chu kỳ.

Một thuật toán phát hiện chu kỳ O(N²) hoạt động tốt ở N=100 gói. Ở N=50.000 gói (một dự án thực tế): mất 17 phút. Sửa chữa O(N): 10 giây.

Lỗi chính xác này tồn tại trong GHC (trình biên dịch Haskell), pip (trình quản lý gói Python), Maven (hệ thống xây dựng Java), Cargo (trình quản lý gói Rust), & 1.000+ dự án khác.

Không phải vì các tác giả của chúng lơ là. visited = [] được viết khi N nhỏ. Mã tôi nước. N tăng lên. Không ai để ý cho đến khi bản dựng mất nửa giờ.

Big O là từ vựng giúp bạn đặt tên cho điều đã xảy ra — & sửa chữa nó.

---

Muốn tìm hiểu sâu hơn? Khóa học unhamming của chúng ta bao gồm một chương đầy đủ về Big O, MOAD-0001 (một lỗi O(N²) thực tế được tìm thấy trong 1.000+ dự án mã nguồn mở), & tại sao việc đặt tên cho một mẫu giúp bạn tìm thấy nó ở khắp nơi. Xem Chương Thiếu Tích: Độ Phức Tạp Thuật Toán.

Dự Đoán Thời Gian Xây Dựng

Một hệ thống xây dựng sử dụng phát hiện chu kỳ O(N²).

Thời gian xây dựng đã đo:

- N=100 gói: 0,01 giây

- N=1.000 gói: 1 giây

Với O(N²): thời gian mở rộng theo (N_new / N_old)².

Với O(N): thời gian mở rộng theo (N_new / N_old).