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.
Bloom filter trả lời 'phần tử này có trong tập không' một cách không chính xác: dương tính giả 0,81% ở 10 bit/phần tử, 14,7% ở 4 bit, giảm theo hàm mũ khi thêm bit nhưng không bao giờ về 0. Đổi lại nó không bao giờ báo âm tính giả và chỉ tốn 1,2 MB thay vì 25 MB. Có số hàm băm tối ưu. 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.
Bài mảng con tổng lớn nhất có lời giải chia để trị đẹp như sách giáo khoa, O(n log n). Nhưng đo ra Kadane — một vòng quét O(n) tầm thường — nhanh hơn 20 lần (5,3 so 112 ms ở 10 triệu phần tử) và gọn hơn hẳn. Chia để trị mạnh và tổng quát, nhưng đẹp không đồng nghĩa tối ưu. Tôi đo.
Không thuật toán sắp xếp đơn nào thắng mọi mặt, nên std::sort của C++ ghép quicksort + insertion + heapsort, mỗi cái che điểm yếu cái kia. Ngưỡng insertion chỉ đáng ~14% chứ không nhiều; và cùng mảng đã sắp giết quicksort pivot cuối (331 ms, đệ quy 50000 tầng) thì introsort xong trong 0,27 ms. 'Tốt nhất' là một kiến trúc, không phải một cái tên. Tôi đo.