Đây là một trong những "hiển nhiên" đầu tiên của khoa học máy tính: tìm kiếm nhị phân là O(log n), tìm tuyến tính là O(n), nên nhị phân luôn nhanh hơn — dùng nhị phân, hết chuyện. Nhưng thử hỏi: nếu mảng chỉ có 8 phần tử thì sao? 16? 32? Big-O nói nhị phân vẫn thắng, nhưng Big-O mô tả hành vi khi N lớn — nó cố tình bỏ qua chuyện gì xảy ra với N nhỏ. Tôi đo cả hai cách trên mảng sắp xếp từ 4 tới 1 triệu phần tử trong container gcc:13, và con số cho thấy có một điểm giao: dưới nó, tuyến tính — cái "tệ hơn về Big-O" — lại nhanh hơn.
Vì sao tuyến tính có thể thắng nhị phân
Tìm tuyến tính quét từ đầu mảng tới khi thấy phần tử. Nghe chậm, nhưng nó có ba lợi thế phần cứng: (1) đọc tuần tự nên prefetch nạp trước — các phần tử tới nơi đã sẵn trong cache; (2) điều kiện vòng lặp i < n gần như luôn đúng, nên CPU đoán nhánh chính xác, không bị phạt; (3) hằng số rất nhỏ — mỗi bước chỉ là một phép so sánh và tăng chỉ số.
Tìm nhị phân so a[mid] rồi rẽ trái hoặc phải, lặp lại. Nó làm ít phép so sánh hơn nhiều (log n thay vì n), nhưng trả giá theo hai cách phần cứng: (1) mỗi lần rẽ trái/phải là một nhánh 50/50 mà CPU không đoán được — mỗi lần đoán sai là một branch misprediction, phạt cỡ chục chu kỳ vì phải xả pipeline; (2) mid nhảy tới vị trí xa, không tuần tự, nên ít thân thiện cache/prefetch.
Với mảng nhỏ (vừa trong một hai cache line), số bước của cả hai đều ít, và lợi thế "ít so sánh" của nhị phân không bù nổi cái phạt rẽ nhánh cộng mất tính tuần tự. Nên tuyến tính thắng — tới một điểm giao. Vượt điểm đó, log n bắt đầu áp đảo và nhị phân thắng, càng lúc càng xa.
Đo: điểm giao ở N≈32
Tôi tìm 4 triệu lần trên mảng sắp xếp mỗi kích thước, đo ns mỗi tra cứu:
Mảng sắp xếp (g++ -O2, ns/tra cứu):
N | tuyến tính | nhị phân | ai thắng
------|------------|----------|----------
4 | 1,2 | 1,7 | TUYẾN TÍNH 1,4x
8 | 1,7 | 2,6 | TUYẾN TÍNH 1,5x
16 | 2,8 | 3,6 | TUYẾN TÍNH 1,3x
32 | 4,7 | 4,5 | ~ngang nhau (điểm giao)
64 | 9,1 | 5,3 | nhị phân 1,7x
128 | 20,0 | 6,5 | nhị phân 3,1x
256 | 37,6 | 7,7 | nhị phân 4,9x
1024 | 127,8 | 10,2 | nhị phân 12,5x
1 triệu| (vô vọng)| 100,9 | nhị phân
Nhìn phần trên: với N = 4, 8, 16, tuyến tính nhanh hơn nhị phân (1,3–1,5 lần) — dù Big-O của nó tệ hơn. Ở N = 32 hai cách ngang nhau — đó là điểm giao. Từ N = 64 trở lên, nhị phân thắng, và khoảng cách giãn ra nhanh: 1,7× ở N=64, 12,5× ở N=1024. Tuyến tính tăng tuyến tính theo N (127,8 ns ở N=1024) trong khi nhị phân tăng log (chỉ 10,2 ns) — đúng như Big-O hứa, khi N đủ lớn.
Chú ý thêm dòng N = 1 triệu: nhị phân nhảy lên 100,9 ns (từ 10,2 ns ở N=1024) — vì ở 1 triệu, mảng không vừa cache nữa nên các bước nhị phân sâu chạm bộ nhớ xa, mỗi bước một cache miss. Còn tuyến tính ở 1 triệu thì vô vọng (~500 nghìn so sánh mỗi tra cứu). Big-O rốt cuộc đúng — chỉ là nó nói về vùng N lớn, không phải mọi N.
Một lần tôi đo hớ: "O(log n) < O(n) nên nhị phân luôn thắng"
Tôi vào đo với niềm tin sách vở nguyên xi: "nhị phân O(log n), tuyến tính O(n), nên nhị phân luôn nhanh hơn". Đo phá tan cho vùng N nhỏ: điểm giao ở khoảng N=32, và dưới đó tuyến tính nhanh hơn — vì quét tuần tự thân thiện cache và không có branch misprediction, trong khi nhị phân rẽ 50/50 khó đoán bị phạt. Còn niềm tin gốc rễ hơn: "Big-O quyết định mọi lúc". Sai — Big-O mô tả hành vi tiệm cận, tức là khi N tiến tới lớn; nó cố tình vứt bỏ hằng số và số hạng bậc thấp, những thứ thống trị khi N nhỏ. Với N nhỏ, hằng số và phần cứng (cache, dự đoán nhánh) mới là thứ quyết định.
Bài học đo lường: Big-O là hành vi TIỆM CẬN (N lớn) — với mảng NHỎ, hằng số + cache + dự đoán nhánh quyết định, và tìm tuyến tính (O(n)) có thể nhanh hơn nhị phân (O(log n)) tới một điểm giao (~N=32): dưới đó tuyến tính thắng nhờ quét tuần tự thân thiện cache và không branch misprediction; trên đó nhị phân thắng và bỏ xa (log n). Nếu tôi tin "nhị phân luôn thắng" và dùng nó cho mọi tra cứu — kể cả những tập nhỏ được gọi hàng triệu lần trong vòng nóng — tôi tự làm chậm code so với một vòng quét tuyến tính đơn giản, mà lại còn phức tạp hơn (nhị phân dễ viết sai off-by-one).
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: với tập nhỏ, quét tuyến tính thường là lựa chọn đúng — đơn giản hơn và nhanh hơn. Điểm giao ~16–64 tùy máy và kiểu dữ liệu, nên nếu mảng của bạn thường dưới vài chục phần tử, đừng vội nhị phân. Đây là lý do các thư viện chuẩn chuyển thuật toán theo kích thước: introsort dùng insertion sort (tuyến tính) cho đoạn nhỏ, std::sort/std::lower_bound được tối ưu cho cache, và nhiều cấu trúc (như node lá của B-tree phần 8) quét tuyến tính trong một block nhỏ thay vì nhị phân.
Hệ quả thứ hai: đọc Big-O như hành vi tiệm cận, và biết vùng N thật của bạn. Big-O trả lời "khi dữ liệu lớn gấp đôi, thời gian đổi thế nào" — nó tuyệt vời để chọn giữa các bậc khác nhau (O(n) vs O(n²)) ở quy mô lớn. Nhưng nó không trả lời "cái nào nhanh hơn ở N=20". Với N nhỏ và cố định, hãy đo, đừng suy từ ký hiệu. Một thuật toán "bậc tệ hơn" với hằng số nhỏ và thân thiện cache thường thắng ở kích thước thực tế.
Hệ quả thứ ba là tinh thần đo lường: hằng số và phần cứng — cache, dự đoán nhánh — là thật, và chúng thống trị ở N nhỏ. Con số mang theo: tìm nhị phân O(log n) không phải LÚC NÀO cũng thắng tuyến tính O(n): điểm giao ~N=32 (mảng sắp xếp) — N<32 tuyến tính nhanh hơn (N=4: 1,2 vs 1,7 ns) nhờ quét tuần tự thân thiện cache/prefetch + không branch misprediction; N>32 nhị phân thắng và bỏ xa (N=1024: 10,2 vs 127,8 ns). Big-O là hành vi TIỆM CẬN (N lớn); với N nhỏ hằng số + phần cứng quyết định. Tập nhỏ -> quét tuyến tính (đơn giản + nhanh). O(log n) < O(n) chỉ đảm bảo thắng khi N đủ lớn.
Thử ba mươi giây
Viết hai hàm tìm trên một mảng đã sắp xếp: một quét tuyến tính, một nhị phân. Đo thời gian tra cứu trung bình (gọi hàng triệu lần để ổn định) cho các kích thước mảng khác nhau: 8, 16, 32, 64, 128, 1024. Bạn sẽ thấy tuyến tính nhanh hơn ở kích thước nhỏ, rồi có một điểm — thường quanh vài chục phần tử — mà nhị phân vượt lên, và từ đó nó bỏ xa. Điểm giao chính xác phụ thuộc máy bạn (cache line, tốc độ dự đoán nhánh), nên đo trên chính máy sẽ chạy code là cách duy nhất biết chắc. Ba mươi giây đó cho bạn thấy điều mà "O(log n) < O(n)" giấu đi: bất đẳng thức Big-O chỉ đúng tiệm cận — ở kích thước nhỏ, hằng số nhỏ và phần cứng thân thiện có thể lật ngược nó. Chọn thuật toán theo kích thước thật của dữ liệu, không theo ký hiệu.
