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.
O(n²) nghe như luôn thua O(n log n), nhưng đo ra sai hai lần: ở mảng nhỏ (tới ~128 phần tử) insertion sort nhanh hơn quicksort, và trên mảng đã sắp nó chỉ O(n) — 0,09 ms so với quicksort 1,7 ms, nhanh hơn 19 lần. Big-O là ca xấu nhất tiệm cận; n nhỏ và dữ liệu có sẵn thứ tự thì khác hẳn. 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.
Tưởng độ sâu đệ quy tùy ý, nhưng ngăn xếp OS chỉ 8 MB, mỗi khung ~13 byte, nên có trần cứng ~655.000 lần gọi rồi segfault không một lời cảnh báo. Và bất ngờ: đệ quy KHÔNG chậm hơn vòng lặp (22,8 so 22,7 µs) — cái đắt của nó là trần ngăn xếp, không phải tốc độ. Cách chữa: ngăn xếp tường minh trên heap. Tôi đo.
Fibonacci đệ quy khớp y hệt định nghĩa toán học, nhưng đo ra nó nổ theo hàm mũ: fib(43) gọi 1,4 tỉ lần, mất 447 ms, vì tính lại bài con chồng lấn. Quy hoạch động chỉ là 'nhớ để khỏi tính lại': memo đưa về 85 lời gọi, dưới 1 micro giây. Tabulation nhanh hơn memo 28 lần và không tràn ngăn xếp. Tôi đo.
Tưởng CPU luôn chạy theo thứ tự mình viết, còn reorder bộ nhớ chỉ là lý thuyết trong sách? Tôi đo litmus store-buffer trên ARM: reorder xảy ra thật (11 ca trong 60 triệu vòng), rào dmb ish dập được về 0. Nhưng nó hiếm tới ~1 trên 5,5 triệu vòng — nên code sai vẫn qua sạch mọi test rồi nổ ở production.