Đây là bài mở đầu một sê-ri mới: giải thuật và cấu trúc dữ liệu, đo thật. Chúng ta sẽ không dừng ở big-O trên giấy mà chạy chương trình thật, bấm đồng hồ, và xem lý thuyết khớp — hay lệch — với thực tế đo được thế nào. Và bài đầu tiên đi thẳng vào hiểu lầm phổ biến nhất về big-O: tưởng nó cho biết thuật toán nào nhanh hơn. Tôi vào bài với đúng hiểu lầm đó, và cái đồng hồ chỉnh lại cho tôi.
Big-O là hình dạng, không phải tốc độ
Ký hiệu big-O mô tả thời gian chạy tăng thế nào khi kích thước đầu vào n lớn dần — nó là hình dạng của đường cong khi n tiến tới vô cùng, không phải một con số tốc độ ở một n cụ thể. O(n²) nghĩa là "n gấp đôi thì thời gian gấp bốn"; O(n log n) nghĩa là "gần như gấp đôi". Câu "O(n log n) tốt hơn O(n²)" chỉ đúng theo nghĩa: khi n đủ lớn, đường cong n log n nằm dưới đường cong n². Nó không nói gì về n nhỏ.
Lý do là big-O bỏ qua hằng số. O(n²) thật ra là c₁·n² và O(n log n) là c₂·n·log n, với những hằng số c mà ký hiệu giấu đi. Ở n nhỏ, chính những hằng số bị giấu đó — chứ không phải số mũ — quyết định ai nhanh hơn. Và đó là chỗ tôi đo hớ.
Một lần tôi đo hớ: thuật toán "tốt hơn" lại chậm hơn
Tôi so hai thuật toán sắp xếp: insertion sort (O(n²), một vòng lặp gọn gàng) và merge sort (O(n log n), đệ quy chia đôi rồi trộn). Theo big-O, merge sort thắng, nên phản xạ của tôi là "cứ dùng merge sort cho mọi trường hợp". Tôi viết cả hai bằng C, biên dịch -O2, chạy trên cùng dữ liệu ngẫu nhiên (seed cố định), đo bằng clock_gettime và lấy trung vị nhiều lần chạy. Kết quả:
n insertion(O(n²)) merge(O(n log n)) nhanh hơn
32 83 ns 166 ns insertion
64 292 ns 375 ns insertion
128 1208 ns 833 ns merge
1024 67 µs 8,7 µs merge
65536 259 ms 2,7 ms merge
262144 4,26 GIÂY 13 ms merge
Ở n = 64, insertion sort nhanh hơn merge sort (292 so với 375 ns). Cái thuật toán "tệ hơn về big-O" lại thắng. Lý do: merge sort mang một hằng số ẩn lớn — mỗi lần chia đôi là một lần gọi hàm đệ quy, cấp phát mảng tạm, và chép qua chép lại; còn insertion sort chỉ là một vòng lặp trong bộ nhớ liền mạch, gần như không có phí tổn. Ở n nhỏ, phần n² chưa đủ lớn để lấn át, nên hằng số nhỏ của insertion sort thắng.
Có một điểm giao (crossover) giữa n = 64 và n = 128: dưới nó insertion nhanh hơn, trên nó merge nhanh hơn. Và một khi n lớn thật, big-O thắng áp đảo: ở n = 262144, insertion sort mất 4,26 giây còn merge sort chỉ 13 mili giây — nhanh hơn 325 lần. Cái sai của tôi là gán "big-O tốt hơn" thành "luôn nhanh hơn". Đúng ra big-O chỉ hứa hẹn về hình dạng khi n lớn, và ở n của bạn có thể là chuyện khác hẳn.
Đáng nói: đây không phải một chuyện lý thuyết cho vui. Chính vì điểm giao này mà các thư viện sắp xếp thật (introsort của C++, timsort của Python/Java) dùng insertion sort cho các mảng con nhỏ rồi mới chuyển sang thuật toán O(n log n) cho phần lớn — họ khai thác đúng cái crossover ta vừa đo.
Đo đường cong, không đo một điểm
Bẫy thứ hai ẩn trong chính cách đo. Nếu tôi chỉ đo ở một giá trị n, tôi sẽ kết luận sai theo hai hướng: đo ở n lớn thì "luôn dùng merge", đo ở n nhỏ thì "luôn dùng insertion". Sự thật chỉ hiện ra khi đo cả đường cong — nhiều giá trị n trải rộng — để thấy hình dạng và điểm giao. Một phép đo tại một điểm không cho biết độ dốc.
Và độ dốc chính là thứ xác nhận big-O. Nhìn cột insertion: từ n = 4096 lên n = 65536, n tăng 16 lần, thời gian tăng khoảng 258 lần — xấp xỉ 16², đúng dấu hiệu O(n²). Cột merge tăng chậm hơn nhiều, gần tuyến tính (có thêm chút cho thừa số log). Đây là cách kiểm chứng một tuyên bố big-O bằng đo đạc: vẽ log-log và xem độ dốc có khớp số mũ không.
Phương pháp đo cho cả sê-ri
Vì đây là bài mở, xin nói rõ cách đo sẽ dùng suốt sê-ri, để mọi con số đáng tin. Một, dùng cùng dữ liệu cho các thuật toán so với nhau (seed ngẫu nhiên cố định), để khác biệt là do thuật toán chứ không do đầu vào. Hai, biên dịch ở mức tối ưu thật (-O2) — đo code chưa tối ưu là đo một thứ không ai chạy. Ba, lặp nhiều lần và lấy trung vị, không lấy trung bình: ở n nhỏ thời gian chỉ vài chục nano giây, sát ngưỡng nhiễu của đồng hồ và của hệ điều hành, nên một lần chạy đơn lẻ vô nghĩa (ở n = 8, chênh lệch 41 so với 42 ns nằm trong sai số — tôi không kết luận gì ở đó). Bốn, tin đồng hồ (thời gian thật đo được) hơn suy luận lý thuyết khi hai cái lệch nhau.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: biết n của bạn trước khi chọn thuật toán. Nếu bạn luôn sắp xếp những mảng vài chục phần tử, thuật toán O(n²) đơn giản có thể nhanh hơn và ít lỗi hơn một thuật toán O(n log n) phức tạp. Big-O quan trọng khi n lớn hoặc có thể lớn; ở quy mô nhỏ cố định, hằng số và sự đơn giản mới đáng cân.
Hệ quả thứ hai: big-O là công cụ để suy luận về khả năng mở rộng, không phải để tiên đoán tốc độ tuyệt đối. Con số mang theo — cũng là tinh thần mở màn cho cả sê-ri: big-O mô tả hình dạng đường cong khi n tiến vô cùng, không phải tốc độ ở một n cụ thể; hằng số ẩn quyết định ở n nhỏ, nên insertion sort O(n²) nhanh hơn merge sort O(n log n) ở n=64 (292 so 375 ns) dù thua đậm ở n lớn (4,26 giây so 13 ms tại n=262144); phải đo cả đường cong để thấy điểm giao, và độ dốc log-log xác nhận số mũ. Đừng chọn thuật toán chỉ bằng big-O trên giấy — đo ở quy mô thật của bạn.
Thử ba mươi giây
Không cần viết code: chỉ cần một phép nhẩm. Lấy hai thuật toán bạn đang phân vân — giả sử một cái 100·n (hằng số lớn, big-O tốt) và một cái n² (hằng số nhỏ, big-O xấu). Ở n = 10, cái thứ nhất là 1000, cái thứ hai là 100 — thuật toán "tệ" nhanh gấp mười. Ở n = 1000, cái thứ nhất là 100.000, cái thứ hai là 1.000.000 — giờ thuật toán "tốt" mới thắng. Điểm giao ở đâu? Giải 100n = n² ra n = 100. Ba mươi giây đó cho bạn thấy điều cả bài đo: hằng số quyết định bên dưới điểm giao, số mũ quyết định bên trên — và bạn phải biết mình đang ở phía nào.
