Cây tìm kiếm nhị phân được dạy là O(log n). Nhưng đổ khóa đã sắp (id tăng, timestamp — rất thường gặp) vào thì nó thoái hóa thành xâu: chiều cao 40000 thay vì 34, tra 32672 ns thay vì 51 ns, chậm 640 lần đúng bằng quét tuyến tính. Và một mảng nhị phân đẹp cache cũng không nhanh hơn cây cân bằng. Tôi đo.
AVL sửa cây tìm kiếm suy biến: cùng khóa đã sắp, chiều cao 40000 xuống 16, tra 32538 ns xuống 215 ns. Nhưng trên khóa ngẫu nhiên AVL hơn không đáng kể mà tốn 27906 phép xoay — cân bằng là bảo hiểm cho ca xấu, không phải quà miễn phí. Và cùng cây cân bằng, bố cục bộ nhớ làm tra chênh 6 lần. Tôi đo.
Đếm số so sánh thì B-tree thua tìm nhị phân (bậc 64 làm 100 so với 20). Đo thời gian thì thắng (70 ns so với 98 ns) vì chỉ 4 lần nạp bộ nhớ thay vì 22 — số so sánh nói dối, đồng hồ nói thật. Và có bậc B tối ưu quanh cỡ dòng cache, không phải càng lớn càng nhanh. Tôi đo.
Chèn từng phần tử để dựng heap 'phải là' O(n log n). Nhưng đo dữ liệu ngẫu nhiên thì nó phẳng 2,3 thao tác/phần tử — cũng O(n). O(n log n) chỉ hiện ở ca xấu (chèn giảm dần): thao tác leo 16→22 theo log n. Heapify thì O(n) bất kể đầu vào. Và heap không sắp xếp — nó chỉ cho min rẻ. Tôi đo.
Quicksort là O(n log n) — nên nhiều người vô tư lấy pivot phần tử cuối. Nhưng trên mảng đã sắp (rất thường gặp) nó thành O(n²): thời gian gấp 4 mỗi khi n gấp đôi, ~3000 lần chậm hơn ở 1 triệu, và đệ quy sâu n tầng tràn ngăn xếp. Trung vị-của-3 cứu: về 9 ms. Tôi đo.
Merge sort cùng O(n log n) với quicksort nhưng đo ra chậm hơn 1,25 lần. Tôi đổ lỗi cho malloc trong bước trộn — đo lại thì malloc chỉ chiếm +6%, thủ phạm thật là chép dữ liệu qua đệm (+23 ms). Giá trị thật của merge không phải tốc độ mà là ổn định (0 vs 488.887 cặp đảo) và không có ca xấu. Tôi đo.