Suốt sê-ri này, Big-O luôn xuất hiện như một cái khung — nhưng nó là lý thuyết, một tuyên bố về hành vi khi n tiến tới vô cùng. Câu hỏi thực dụng: làm sao kiểm chứng độ phức tạp bằng đo, và tại sao đường cong thời gian thật thường không giống lý thuyết? Nhiều người tin "cứ chạy thử vài kích thước, nhìn thời gian là biết O mấy" — hoặc ngược lại, "thực tế khác lý thuyết nhiều nên Big-O vô dụng". Tôi đo cả hai trong container gcc:13: một phép tính tổng O(n), một std::sort O(n log n), và một phép truy cập ngẫu nhiên để lộ cache. Con số cho thấy đo ẩu thì lừa mắt, nhưng đo đúng cách thì Big-O khớp lý thuyết đẹp đến bất ngờ.
Tỉ số T(2n)/T(n), và cái bẫy cache
Cách kiểm chứng độ phức tạp bằng thực nghiệm là nhân đôi n và xem thời gian đổi thế nào — tỉ số T(2n)/T(n) tiết lộ bậc:
- O(n): nhân đôi n → thời gian gấp đôi → tỉ số → 2.
- O(n log n): tỉ số hơi hơn 2 (~2,05–2,15), vì thừa số log tăng nhẹ khi n gấp đôi.
- O(n²): tỉ số → 4. O(log n): tỉ số → ~1.
Nghe đơn giản, nhưng đường cong thật có hai cái bẫy khiến đo ẩu ra kết quả sai:
- n nhỏ: chi phí khởi động (cấp phát, làm nóng cache, độ phân giải thô của đồng hồ) lấn át thời gian thực của thuật toán. Ở n nhỏ, tỉ số nhảy lung tung, chưa "ra dáng" tiệm cận.
- Cache gãy khúc: khi vùng làm việc vượt L1 → L2 → L3 → RAM, chi phí mỗi phần tử NHẢY lên (truy cập RAM chậm ~100 lần L1). Một vòng lặp đúng là O(n) có thể trông dốc hơn tuyến tính khi n vượt cache — không phải sai bậc, mà hằng số thay đổi theo tầng bộ nhớ.
Đo: tỉ số hội tụ đúng — nếu đo đúng chỗ
Tôi đo ba thứ, mỗi thứ với n nhân đôi, lấy min của nhiều lần chạy:
g++ -O2:
A. O(n) tính tổng — tỉ số T(2n)/T(n):
n nhỏ (1k–32k) : 1,00 / 4,00 / 1,75 (nhiễu — overhead + timer thô lấn át)
n lớn (>64k) : 2,00 / 2,07 / 2,00 / 2,01 / 2,02 / 1,99 -> HỘI TỤ về 2
B. CACHE gãy khúc — ns mỗi truy cập ngẫu nhiên (đuổi con trỏ):
32 KB (L1) : 0,91 ns
256 KB (L2) : 3,52 ns
2 MB (L3) : 6,42 ns
16 MB (L3) : 10,85 ns
128 MB (RAM): 95,75 ns -> nhảy ~100 lần từ L1 tới RAM
C. O(n log n) std::sort:
ns / (n·log2 n) : ~2,0 (gần như HẰNG SỐ mọi n) -> đúng O(n log n)
T(2n)/T(n) : ~2,07 -> hơn 2 chút vì thừa số log
Nhìn A — kiểm chứng O(n): ở n nhỏ (1k–32k), tỉ số T(2n)/T(n) lung tung (1,00, rồi 4,00, rồi 1,75) — hoàn toàn không giống "2". Đó là vì thời gian quá nhỏ, độ phân giải đồng hồ và overhead khởi động lấn át. Nhưng từ n > 64k trở đi, tỉ số hội tụ về 2,00 (2,00, 2,07, 2,00, 2,01, 2,02, 1,99) — đúng như O(n) hứa. Bài học: phải đo ở n đủ lớn mới thấy tiệm cận.
Nhìn B — cái bẫy cache: đây là chỗ đường cong "lừa mắt". Cùng một thao tác "truy cập một phần tử", nhưng ns mỗi lần nhảy theo tầng cache: 0,91 ns khi dữ liệu ở L1, 3,52 ns ở L2, 6,42–10,85 ns ở L3, và 95,75 ns khi ra RAM — chậm hơn ~100 lần. Nghĩa là một vòng lặp "O(n)" đọc dữ liệu ngẫu nhiên sẽ có ns mỗi phần tử không hằng số: nó nhảy vọt khi n vượt cache. Nếu bạn đo thời gian tổng và vẽ đường cong qua các mốc cache, nó trông cong lên như siêu tuyến tính — dù bậc vẫn là O(n). Hằng số đổi, không phải bậc.
Nhìn C — kiểm chứng O(n log n): std::sort cho ns/(n·log₂n) gần như hằng số ~2,0 ở mọi n — dấu hiệu chắc chắn của O(n log n). Và tỉ số T(2n)/T(n) là ~2,07, đúng hơn 2 một chút như lý thuyết dự đoán (thừa số log). Đo đúng cách, số khớp lý thuyết đẹp không ngờ.
Một lần tôi đo hớ: "đo thời gian là biết ngay độ phức tạp" và "Big-O vô dụng vì thực tế khác"
Tôi vào đo với sự tự tin: "cứ chạy vài kích thước, nhìn thời gian là biết O mấy". Đo phá tan: ở n nhỏ, tỉ số T(2n)/T(n) nhảy lung tung (1,00, 4,00, 1,75) vì hằng số và overhead lấn át — nếu tôi kết luận từ đó, tôi sẽ đoán sai bậc. Tệ hơn, cache gãy khúc làm ns mỗi phần tử nhảy ~100 lần khi vượt L1/L2/L3 — một O(n) thẳng thớm trông cong lên như O(n log n) hay tệ hơn nếu tôi đo ngang qua các mốc cache. "Nhìn thời gian là biết độ phức tạp" là sai nếu đo ẩu: n phải đủ lớn, phải cùng tầng cache, phải lấy min nhiều lần.
Nhưng đo cũng phá luôn niềm tin ngược mà người đã vấp cache dễ rơi vào: "thực tế lộn xộn thế này thì Big-O lý thuyết vô dụng, chỉ đo là đủ". Sai: khi tôi đo đúng cách — tỉ số T(2n)/T(n) ở n đủ lớn, cùng tầng cache, min của nhiều lần — kết quả hội tụ chính xác về lý thuyết: O(n) → 2,00, O(n log n) → 2,07 với ns/(n log n) hằng số. Big-O đúng ở tiệm cận; nó chỉ không mô tả vùng n nhỏ và không nói về hằng số (cache). Vứt bỏ Big-O vì đường cong thô lộn xộn là vứt đi công cụ dự đoán bậc — thứ quyết định khi n lớn.
Bài học đo lường: kiểm chứng độ phức tạp bằng tỉ số T(2n)/T(n): O(n)→2, O(n log n)→~2,07, O(n²)→4. NHƯNG đường cong thật lừa mắt vì (1) n nhỏ: overhead + hằng số + timer thô lấn át (tỉ số lung tung 1,0/4,0/1,75); (2) CACHE gãy khúc: ns/phần tử nhảy ~100x khi vượt L1(0,9ns)→RAM(96ns), làm O(n) trông siêu tuyến tính. Đo ĐÚNG (n đủ lớn, cùng tầng cache, min nhiều lần) thì hội tụ chính xác: O(n)→2,00, O(n log n)→2,07 (ns/(n log n) hằng số). Big-O đúng ở TIỆM CẬN; đường cong thực = Big-O × hằng số ẩn. Nếu tôi tin "đo là biết ngay" tôi đoán sai bậc từ vùng nhiễu; nếu tin "Big-O vô dụng" tôi vứt công cụ dự đoán quy mô.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: muốn kiểm chứng độ phức tạp, dùng tỉ số T(2n)/T(n) ở n đủ lớn — đừng đoán từ vài điểm nhỏ. Nhân đôi n vài lần, lấy min của nhiều lần chạy, và xem tỉ số hội tụ về đâu (2 → O(n), ~2 hơn chút → O(n log n), 4 → O(n²)). Bỏ qua các điểm n nhỏ (nhiễu) và để ý xem có gãy khúc cache không. Đây là cách xác nhận một thuật toán thực sự có bậc bạn nghĩ, hay có một O(n²) ẩn.
Hệ quả thứ hai: khi đường cong thật "cong lên" bất thường, nghi cache trước khi nghi sai bậc. Một thao tác O(n) chậm dần khi dữ liệu lớn thường là do vượt cache (ns/phần tử nhảy tầng), không phải vì nó bí mật là O(n log n). Kiểm bằng cách đo trong cùng một tầng cache, hoặc nhìn kích thước dữ liệu so với L2/L3. Nhầm gãy khúc cache thành "sai độ phức tạp" dẫn tới tối ưu sai chỗ.
Hệ quả thứ ba là tinh thần đo lường: Big-O cho bạn bậc; đo cho bạn hằng số. Cả hai cần nhau. Con số mang theo: đường cong thực = Big-O × hằng số ẩn (cache, overhead). Kiểm bậc bằng tỉ số T(2n)/T(n) ở n đủ lớn cùng tầng cache — hội tụ đúng (O(n)→2,00, O(n log n)→2,07). n nhỏ nhiễu, cache gãy khúc (L1 0,9ns → RAM 96ns, ~100x) làm đường cong lừa mắt. Dùng Big-O để biết quy mô lớn, đo để biết hằng số ở quy mô của bạn. Đừng chọn giữa lý thuyết và đo — dùng lý thuyết cho bậc, đo cho hằng số.
Thử ba mươi giây
Viết một phép tính tổng mảng và bấm giờ với n gấp đôi liên tục (1000, 2000, 4000, …, vài chục triệu), in tỉ số thời gian của mỗi bước so với bước trước. Bạn sẽ thấy ở n nhỏ tỉ số lung tung (đồng hồ quá thô, overhead lấn át), rồi từ một ngưỡng nào đó nó ổn định về ~2 — đó là O(n) hiện ra khi n đủ lớn. Rồi làm một thí nghiệm cache: tạo một hoán vị ngẫu nhiên và "đuổi con trỏ" (mỗi bước nhảy tới chỉ số ngẫu nhiên tiếp theo) với các vùng làm việc 32 KB, 256 KB, 2 MB, 128 MB, đo ns mỗi bước — bạn sẽ thấy nó nhảy vọt theo tầng cache, từ dưới 1 ns lên gần 100 ns. Cuối cùng, std::sort với n gấp đôi và in ns/(n·log₂n): nó gần như hằng số, xác nhận O(n log n). Ba mươi giây đó cho bạn thấy điều mà cả "đo là biết ngay" lẫn "Big-O vô dụng" đều giấu đi: đo đúng cách thì lý thuyết và thực tế gặp nhau — Big-O nói bậc, đo nói hằng số, và cache là lý do đường cong thô không bao giờ mượt như sách vẽ.
