LRU chỉ cần một map, quét tìm phần tử cũ khi đuổi? Tôi đo thử: quét map tìm phần tử ít dùng nhất là O(n) — cache 100 nghìn thì mỗi lần đuổi mất 128 µs, chậm 5862 lần bản đúng. LRU O(1) phải kết hợp hash map (tra O(1)) với danh sách liên kết đôi (thứ tự dùng O(1)). Sức mạnh nằm ở sự kết hợp.
Ma trận kề đơn giản nên cứ dùng? Tôi đo thử: với đồ thị thưa (đa số thực tế), ma trận tốn RAM gấp 127 lần và duyệt chậm 302 lần vì phải quét cả V² ô. Danh sách kề chỉ lưu cạnh thật. Nhưng ma trận lại thắng khi cần hỏi 'có cạnh (i,j) không' — O(1). Chọn theo mật độ đồ thị.
BFS và DFS chỉ khác thứ tự duyệt, bộ nhớ như nhau? Tôi đo thử: trên cây phân nhánh cao, hàng đợi BFS giữ 1 triệu đỉnh cùng lúc còn ngăn xếp DFS chỉ 1.999 — chênh 500 lần. Trên đồ thị sâu, DFS đệ quy tràn stack và sập ở độ sâu ~500 nghìn. Bộ nhớ phụ thuộc hình dạng đồ thị, không phải cái nào cũng như nhau.
Sắp xếp nào cũng như nhau, cứ std::sort? Tôi đo thử: sắp tại chỗ tốn ~0 bộ nhớ phụ nhưng không ổn định; sắp cấp thêm (merge) tốn 80 MB buffer cho 20 triệu int nhưng giữ thứ tự phần tử bằng nhau. Và quicksort pivot xấu trên dữ liệu đã sắp xếp thành O(n²), chậm 2428 lần.
Nhiều if-else cũng nhanh như switch, compiler lo hết? Tôi đo thử: chuỗi quét tuyến tính là O(N) — 256 nhánh mất 35,57ns còn bảng nhảy 0,24ns, chậm 121 lần. Nhưng ở 2-4 nhánh, if-else viết tay ngang bảng, và phân bố lệch làm branch prediction gần miễn phí. Đây là một điểm giao, không phải câu trả lời một chiều.
std::string luôn cấp phát heap nên chậm? Tôi đo thử: nhờ SSO, chuỗi ngắn (≤15 ký tự) lưu inline ngay trong đối tượng 32 byte, không malloc — tạo nhanh gấp 3 lần và copy nhanh gấp 5,3 lần chuỗi dài phải malloc. Phần lớn chuỗi thực tế đều ngắn nên chẳng bao giờ chạm heap.