Thêm vào mảng động là O(1) khấu hao, nhưng đo đường cong từng thao tác thấy gai O(n): lần cấp phát cuối sao chép 2,1 triệu phần tử mất 392µs, gấp 400.000 lần một lần thêm thường. Và tăng dung lượng mỗi lần +1 để 'tiết kiệm bộ nhớ' hóa ra là O(n²), chậm 17.851 lần. Tôi đo cả đường cong.
Quicksort pivot cố định gặp mảng đã sắp xếp làm 2,05 tỉ so sánh (901 ms); pivot ngẫu nhiên chỉ 1,3 triệu (1,1 ms) — ít hơn 1524 lần. Và skip list cân bằng bằng tung đồng xu, đạt ~log n mà không một phép xoay. Gieo ngẫu nhiên đúng chỗ là tăng an toàn, không phải thêm rủi ro. Tôi đo.
Bitset nhỏ hơn mảng bool 8 lần, giao hai tập bằng AND nhanh 12,9 lần (64 phần tử mỗi lệnh). Nhưng đặt một bit lẻ chậm hơn ghi một byte 1,46 lần khi vừa cache — rồi nhanh hơn 6,3 lần khi tràn cache. Lợi thật của bitset là mật độ cache, không phải mẹo bit. Tôi đo cả đường cong.
LRU cài đúng đạt O(1) nhờ băm + danh sách liên kết đôi (nhanh 323 lần bản O(n) ở cache 10.000). Nhưng cache to gấp 25 lần chỉ thêm 37 điểm hit, và một lượt quét tuần tự lớn hơn cache khiến LRU trúng 0% — đuổi ngẫu nhiên lại được 41,6%. Hiệu quả cache phụ thuộc hoàn toàn vào mẫu truy cập. Tôi đo.
Mỗi truy vấn suffix array nhanh hơn KMP 18.554 lần (0,21 µs so 3.869 µs) — nhưng phải dựng mảng trước, tốn 358 ms cho văn bản 2 triệu ký tự. Cho một lần tìm, KMP thắng đậm; suffix array chỉ có lãi sau ~93 truy vấn trên cùng văn bản. 'Nhanh nhất' vô nghĩa nếu chưa hỏi tìm bao nhiêu lần. Tôi đo.
Chia việc cho 10 lõi tưởng nhanh gấp 10, nhưng đo ra: việc song song thuần nhất chỉ đạt 7,38x, thêm 10% việc tuần tự tụt còn 4,53x (khớp luật Amdahl), và việc nghẽn băng thông bộ nhớ chỉ 3,28x vì mọi lõi tranh một bus. Phần tuần tự nhỏ bé mới là thứ đặt trần. Tôi đo.