Giải thuật và cấu trúc dữ liệu: đo thật

Sê-ri đo đạc: giải thuật và cấu trúc dữ liệu thật sự chạy nhanh chậm thế nào trên máy thật — không chỉ big-O trên giấy. Đo thời gian, bộ nhớ, cache, số phép bằng chương trình nhỏ trong container dùng một lần, và tìm chỗ thực tế lật ngược lý thuyết.

2/45 phần đã đăng Giải thuật

1 Big-O và thực tế đo được Định chọn merge sort cho mọi trường hợp vì O(n log n) tốt hơn O(n²). Nhưng đo ra ở n=64 insertion sort nhanh hơn (292 so 375 ns) vì hằng số ẩn. Big-O là hình dạng khi n tiến vô cùng, không phải tốc độ ở n cụ thể — phải đo cả đường cong, không đo một điểm. Đo thật bằng C. 03/09/2026 · 7 phút đọc 2 Mảng và cache Hai vòng lặp làm đúng cùng số phép load và cộng, cùng O(n) — tôi đếm phép rồi tưởng cùng tốc độ. Đo ra duyệt ngẫu nhiên chậm 452 lần duyệt tuần tự trên mảng 256MB. Chi phí thật không ở phép cộng mà ở truy cập bộ nhớ: cache và prefetch. Đo thật bằng C. 03/09/2026 · 7 phút đọc

Còn 43 phần nữa sẽ lần lượt được đăng.