Tưởng duyệt mảng và danh sách liên kết tốn như nhau vì cùng O(n)? Tôi đo thử: duyệt 20 triệu phần tử, mảng 0,24ns/phần tử còn linked list 104ns — chậm 442 lần, vì mỗi con trỏ next là một cache miss còn mảng thì được prefetch. Big-O đếm số thao tác, không đếm giá mỗi thao tác.
Tưởng mỗi push_back copy cả mảng nên vector chậm, hoặc grow-by-1 tiết kiệm RAM nên tốt? Tôi đo thử: nhân đôi amortize xuống 2,57ns/push (O(1)) xây 20 triệu phần tử, còn grow-by-1 là O(N²) — chỉ 50 nghìn phần tử đã 1,25 tỷ copy, 3213ns/push, nếu 20 triệu thì mất 7 giờ.
Ai cũng thuộc 'linked list chèn/xóa O(1), mảng O(N)'. Tôi đo thử: chèn ở đầu list nhanh hơn mảng 70.000 lần — nhưng chèn giữa THỰC TẾ (phải tìm vị trí trước) thì list lại chậm hơn mảng 16 lần, vì duyệt để tìm là cache miss mỗi bước. O(1) chỉ đúng khi đã cầm sẵn con trỏ.
Ai cũng nói hash table là O(1). Tôi đo thử: O(1) chỉ đúng khi hệ số tải thấp — tải 0,25 tốn 1,17 probe (3,2ns), nhưng đẩy tải lên 0,99 thì probe trung bình nổ lên 43 và tra cứu chậm 10 lần. O(1) là trung bình có điều kiện, không phải bảo đảm vô điều kiện.
Phần 4 cho thấy tải cao giết hash table. Nhưng tôi đo tiếp: ngay ở CÙNG tải 0,70, đổi hàm băm tốt sang xấu làm probe trung bình nhảy từ 2,17 lên 358,9 — tra cứu chậm 23 lần. Băm hằng số thì thoái hóa hoàn toàn về O(n). Tải thấp là điều kiện cần, không đủ.
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.