Đổi tiền bằng cách chộp đồng xu lớn nhất luôn đúng với hệ {1,5,10,25}. Nhưng đo hệ khác thì nó sai 25-40% số tiền — hệ {1,7,10}, số 14: tham lam 5 xu, tối ưu 2 xu. Tham lam nhanh hơn quy hoạch động 100 triệu lần cho một truy vấn (2,1 ns so 228 ms), nhưng nhanh mà sai thì vô dụng. 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.
BFS và DFS được dạy như cặp sinh đôi cùng O(V+E), nên tưởng thay thế được. Nhưng trên lưới 1000×1000 chúng tìm thứ khác hẳn: BFS ra đường ngắn nhất 1998 cạnh, DFS ra đường 499.500 cạnh — dài gấp 250 lần. Bộ nhớ cũng phình theo hai chiều khác nhau. 'Cùng độ phức tạp' không có nghĩa 'cùng việc'. Tôi đo.
Dijkstra là thuật toán tham lam nhưng đúng — nhờ đúng một điều kiện: trọng số không âm. Cho nó một cạnh âm (2→1 = -3), nó chốt dist[1]=4 sai trong khi đáp án thật là 2, mà không một cảnh báo. Và cấu trúc bên trong quyết định quy mô: heap nhanh hơn mảng 36 lần trên đồ thị thưa. Tôi đo.
Union-Find không tự nhiên O(1): bản naive để cây thoái hóa thành chuỗi, đường find trung bình 9999 (=n/2), find hết mất 88 ms. Hai tối ưu vài dòng ép đường find về ~1, nhanh 3000 lần — và đẹp nhất, ở 10 triệu phần tử đường find trung bình vẫn phẳng lì ở 1,01. 'Gần O(1)' là sự thật đo được. Tôi đo.
Sách bảo naive O(n·m) chậm, phải dùng KMP. Nhưng trên văn bản ngẫu nhiên naive chỉ 1,04 so sánh mỗi ký tự — gần O(n), còn nhỉnh hơn KMP. O(n·m) là trường hợp xấu nhất, chỉ bật ra trên văn bản lặp (T='aaaa', P='aa..b') nơi KMP nhanh 194 lần. Nhãn xấu nhất không phải bản án cho mọi đầu vào. Tôi đo.