Đệ quy ngây thơ tính Fibonacci gọi hàm 3,67 tỉ lần cho fib(45) và mất gần 3 giây — vì nó tính đi tính lại cùng một giá trị. Bài này đo thật trong go-lab: thêm một mảng nhớ (memoization) biến O(2^n) thành O(n), nhanh hơn ~4 triệu lần, và giải được fib(90) trong 667 ns. Kèm so sánh memoization với tabulation và đánh đổi bộ nhớ.
Thuật toán tham lam (greedy) chọn phương án tốt nhất ở mỗi bước — nhanh và đơn giản. Nhưng nó chỉ đúng với một số bài toán. Bài này đo thật trong go-lab bài đổi tiền: với bộ mệnh giá 1,5,10,25 greedy cho lời giải tối ưu, nhưng với bộ 1,7,10 để đổi 14 đồng greedy dùng 5 đồng trong khi DP chỉ cần 2. Greedy nhanh hơn DP 9-93 lần nhưng có thể sai; DP luôn đúng nhưng tốn hơn.
BFS và DFS cùng duyệt mọi đỉnh trong O(V+E) — khác nhau ở thứ tự thăm, không ở tốc độ. Nhưng cách BIỂU DIỄN đồ thị thì khác nhau một trời một vực. Bài này đo thật trong go-lab: trên đồ thị thưa 20.000 đỉnh, ma trận kề tốn 391 MB và duyệt chậm hơn danh sách kề 344 lần, trong khi danh sách chỉ dùng 1,68 MB. Vì sao, và khi nào ma trận mới đáng dùng.
Dijkstra tìm đường đi ngắn nhất, nhưng tốc độ của nó phụ thuộc vào một chi tiết: tìm đỉnh gần nguồn nhất bằng cách nào. Bài này đo thật trong go-lab: bản quét mảng O(V²) mất 3,55 giây trên đồ thị thưa 50.000 đỉnh, còn bản dùng heap O((V+E)log V) chỉ 16,9 ms — nhanh hơn 210 lần, cùng kết quả. Nhưng trên đồ thị dày, bản mảng lại cạnh tranh.
Hai vòng lặp cùng số phép tính, cùng độ phức tạp O(n²), nhưng một cái chậm hơn cái kia 14 lần — chỉ vì thứ tự truy cập bộ nhớ. Bài này đo thật trong go-lab: duyệt mảng 2D theo cột chậm hơn theo hàng tới 13,9 lần vì cache. Nhưng cũng trung thực: AoS vs SoA và truy cập ngẫu nhiên lại gần như không khác, vì CPU hiện đại giỏi giấu độ trễ cho mẫu đều đặn.
Mười một bài, mười một phép đo thật trong Docker. Bài tổng kết này nối tất cả thành một bảng số liệu và một checklist thực dụng: cần gì thì dùng cấu trúc nào, khi nào Big-O là yếu tố sống còn (heap top-k 247 lần, Dijkstra 210 lần, memo 4 triệu lần), và khi nào hằng số với cache mới là thứ quyết định (insertion thắng quicksort ở N nhỏ, duyệt cột chậm 14 lần dù cùng O(n²)).