O(1) < O(log n), nên hash luôn hơn cây? Tôi đo thử: tra cứu điểm hash nhanh hơn cây đỏ-đen 32 lần (16ns vs 518ns). Nhưng range query — tìm mọi phần tử >= x theo thứ tự — cây làm trong 7,8µs còn hash phải sort lại toàn bộ, 54,2ms. 'Cái nào nhanh hơn' là câu hỏi sai; chọn theo loại truy vấn.
BST tra cứu O(log n)? Chỉ khi cây cân bằng. Tôi đo thử: chèn dữ liệu ĐÃ sắp xếp vào một BST thường làm cây lệch thành chuỗi cao đúng bằng N (50.000), tra cứu chậm hơn std::map 461 lần và xây cây chậm 594 lần. Dữ liệu sắp xếp — thứ trông đẹp nhất — hóa ra là worst case, không phải best.
Cây nhị phân và B-tree đều O(log n) — vậy sao mọi cơ sở dữ liệu dùng B-tree? Tôi đo thử: tra cứu 4 triệu khóa, cây nhị phân đi 22 tầng (887ns), B-tree fanout 64 chỉ 4 tầng (153ns) — nhanh 5,8 lần. Mỗi tầng là một lần chạm bộ nhớ (hay một lần đọc đĩa), nên ít tầng thắng. Cùng O(log n), khác cơ số log.
Xây một heap từ n phần tử — push từng cái cũng như make_heap chứ gì? Tôi đo thử: n lần push là O(n log n), còn heapify bottom-up là O(n); với dữ liệu xấu nhất heapify nhanh hơn 6,3 lần. Và bất ngờ: heap không cần cây con trỏ — nó chỉ là một mảng liền mạch.
Stack và queue đều O(1) push/pop dù cài bằng mảng hay linked list — chọn cách nào cũng vậy? Tôi đo thử: stack bằng mảng 0,3ns/thao tác, bằng linked list 4,0ns — chậm 13 lần, vì linked list trả malloc+free (5,5ns) mỗi thao tác. Cùng O(1), khác hằng số cả chục lần.
O(log n) < O(n), nên tìm nhị phân luôn thắng tuyến tính? Tôi đo thử: với mảng nhỏ, tuyến tính NHANH HƠN — điểm giao ở khoảng N≈32; dưới đó quét tuần tự thắng nhờ cache và không branch misprediction. Big-O là hành vi tiệm cận (N lớn); N nhỏ thì hằng số và phần cứng mới quyết định.