Giải thuật nâng cao: đo thật độ phức tạp và đánh đổi

Sê-ri 12 phần về giải thuật và cấu trúc dữ liệu nâng cao dưới góc nhìn kỹ sư thực chiến: không chỉ Big-O lý thuyết mà CHẠY THẬT trong Go và ĐO THỜI GIAN để thấy độ phức tạp hiện ra, và vì sao hằng số/cache/cấp phát bộ nhớ khiến thuật toán tốt hơn trên giấy lại chậm hơn thực tế. Mỗi bài so hai ba cách giải cùng bài toán, đo thật thời gian trên nhiều kích thước đầu vào, nêu rõ khi nào chọn cái nào.

12/12 phần đã đăng Lập trình

1 Big-O không phải lý thuyết suông: đo thật để thấy nó hiện ra Ai cũng học Big-O rồi quên, vì nó nghe như toán hàn lâm. Nhưng Big-O là thứ ĐO được. Bài này chạy thật trong go-lab: khi N tăng gấp đôi, O(n) ×2, O(n²) ×4, còn O(log n) gần như đứng yên. Chính tỉ lệ 'nhân đôi N' đó là cách nhận ra độ phức tạp của code bạn — và lý do một hàm O(n²) chạy ngon lúc dev lại làm sập hệ thống lúc scale. 22/09/2026 · 7 phút đọc 2 Linear vs binary search: binary nhanh 1.125 lần, nhưng không phải lúc nào cũng nên dùng Binary search O(log n) nghe là biết thắng linear O(n). Bài này đo thật trong go-lab: ở N=262.144, binary nhanh hơn 1.125 lần một lần tìm. Nhưng binary đòi mảng đã sắp — và chi phí sort trước (306 µs) đổi cục diện: nếu chỉ tìm 1-2 lần trên mảng chưa sắp, linear thắng. Cộng thêm yếu tố cache khiến ở N nhỏ binary chỉ nhỉnh 3,7 lần. 22/09/2026 · 7 phút đọc 3 Quicksort, mergesort hay sort.Ints? Đo thật bốn cách sắp xếp và ba điều bất ngờ O(n²) chậm hơn O(n log n) — ai cũng biết. Nhưng đo thật trong go-lab cho thấy nhiều thứ sách không nói: insertion sort O(n²) lại NHANH HƠN quicksort tự viết ở N=1.000; quicksort tự viết thua mergesort vì cấp phát bộ nhớ; và sort.Ints của thư viện chuẩn (introsort) đánh bại mọi bản tự viết. Cài đặt quan trọng ngang độ phức tạp. 22/09/2026 · 7 phút đọc 4 Hash table O(1): phép màu tra cứu — và ba cách nó sụp đổ về O(n) Map/dict cho tra cứu O(1) — nhanh bất kể dữ liệu lớn cỡ nào. Bài này đo thật trong go-lab: hashtable và map Go giữ ~1-21 ns dù N tăng 256 lần, trong khi quét slice tăng tuyến tính tới 32 µs. Nhưng O(1) chỉ là trung bình: hàm băm tệ (mọi key về một bucket) làm tra cứu chậm gấp 11.874 lần, và quên pre-size map khiến chèn chậm gấp đôi vì rehash. 22/09/2026 · 7 phút đọc 5 Cây tìm kiếm nhị phân: O(log n) hay O(n) tùy cách bạn chèn — và vì sao map Go không dùng cây Cây BST hứa tra cứu O(log n), nhưng chèn dữ liệu đã sắp vào nó một cách ngây thơ thì cây suy biến thành danh sách liên kết O(n). Bài này đo thật trong go-lab: cùng N=64.000, BST cân bằng tra cứu 99 ns còn BST suy biến 29.618 ns — chậm gấp 300 lần. Map Go (hash) còn nhanh hơn cả cây cân bằng. Vậy khi nào mới nên dùng cây? 22/09/2026 · 8 phút đọc 6 Heap và bài toán top-k: vì sao lấy 10 phần tử lớn nhất lại nhanh hơn sắp xếp 247 lần Cần 10 phần tử lớn nhất từ 8 triệu? Sắp xếp cả mảng rồi lấy 10 đầu là cách ai cũng nghĩ tới — và là cách sai. Bài này đo thật trong go-lab: min-heap size k lấy top-10 trong 4,3 ms, còn full sort mất hơn 1 giây — nhanh hơn 247 lần. Kèm cơ chế heap làm hàng đợi ưu tiên với Push/Pop O(log n), nền tảng của Dijkstra và lập lịch. 22/09/2026 · 7 phút đọc 7 Quy hoạch động: vì sao fib(45) mất 2,74 giây với đệ quy nhưng 625 nano giây với memoization Đệ 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ớ. 22/09/2026 · 6 phút đọc 8 Tham lam hay quy hoạch động: khi chọn 'tốt nhất ngay bây giờ' lại cho kết quả tệ nhất 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. 22/09/2026 · 7 phút đọc 9 BFS, DFS và cái giá của ma trận kề: vì sao duyệt đồ thị thưa bằng ma trận chậm hơn 344 lầ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. 22/09/2026 · 7 phút đọc 10 Dijkstra với heap: vì sao đổi cách tìm đỉnh gần nhất biến 3,5 giây thành 17 mili giây 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. 22/09/2026 · 8 phút đọc 11 Cùng O(n²) nhưng chậm hơn 14 lần: phần hiệu năng mà Big-O không nhìn thấy 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. 22/09/2026 · 7 phút đọc 12 Tổng kết: khung tư duy chọn thuật toán — khi nào Big-O quyết định, khi nào thực tế thắng 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²)). 22/09/2026 · 6 phút đọc