Module 1 — Tổng kết & cheat sheet: Nền tảng thuật toán

TL;DR: Module 1 cho bạn 4 công cụ tư duy: Big-O làm ngôn ngữ đo lường, amortized giải thích hành vi trung bình trên cả dãy thao tác, call stack giải thích giới hạn của đệ quy, cache locality giải thích khoảng cách giữa lý thuyết và thực tế. Bài này gom lại cheat sheet, glossary, các bẫy hay gặp, và giúp bạn tự kiểm tra 4 learning outcome của module.

Cheat sheet

Glossary

Big-O (O): ký hiệu chặn trên (upper bound). T(n) = O(f(n)) nếu tồn tại hằng số c và n₀ sao cho với mọi n ≥ n₀, T(n) ≤ c × f(n). Đo tốc độ tăng tiệm cận (asymptotic), không đo thời gian tuyệt đối.

Theta (Θ): Chặn chặt (tight bound): T(n) = Θ(f(n)) khi T(n) bị chặn cả trên lẫn dưới bởi bội số của f(n). Mô tả chính xác hơn O nhưng khó chứng minh hơn.

Omega (Ω): Chặn dưới (lower bound): T(n) = Ω(f(n)) khi T(n) không tăng chậm hơn f(n). Hữu ích trong chứng minh "không thuật toán nào có thể tốt hơn Ω(n log n) cho sắp xếp so sánh".

Amortized cost: Chi phí trung bình của một thao tác trên một dãy thao tác worst-case liên tiếp. Mạnh hơn average case vì không cần giả định về phân bố của input.

Stack frame: Khối bộ nhớ cấp phát trên thread stack mỗi khi một hàm được gọi. Chứa biến cục bộ, tham số, return address và frame pointer. Giải phóng khi hàm return.

TCO (Tail-Call Optimization): Tối ưu hóa biến đệ quy đuôi thành vòng lặp để tái dùng frame thay vì push frame mới. JVM không hỗ trợ ở runtime; Kotlin/Scala thực hiện ở compile time.

Cache line: Đơn vị tối thiểu CPU đọc từ bộ nhớ, phổ biến 64 byte trên x86 và nhiều chip ARM. Đọc một byte trong mảng nạp cả 64 byte liên tiếp vào cache.

Hardware prefetcher: Mạch điện trong CPU dự đoán kiểu truy cập bộ nhớ và nạp trước dữ liệu vào cache. Hoạt động tốt với truy cập tuần tự; vô hiệu khi đuổi theo con trỏ ngẫu nhiên.

Cache miss: Truy cập dữ liệu không có trong cache, buộc CPU lấy từ cấp bộ nhớ chậm hơn. L1 miss → L2 (cỡ 3–10ns); L2 miss → L3 (cỡ 10–30ns); L3 miss → DRAM (cỡ 100ns).

False sharing: Hai thread ghi vào hai biến khác nhau về logic nhưng nằm trên cùng cache line 64 byte. Mỗi lần ghi của thread A làm mất hiệu lực cache line trên core của thread B, gây tranh chấp không cần thiết.

Growth factor: Hệ số nhân khi dynamic array resize: capacity mới = capacity cũ × factor. Java ArrayList dùng 1.5x; C++ libc++ vector dùng 2x. Factor nhỏ hơn golden ratio ~1.618 về lý thuyết cho phép allocator tái dùng block cũ, nhưng allocator thật không nhất thiết làm vậy; lý do chính vẫn là đánh đổi giữa số lần resize và RAM thừa.

Potential method: Một trong ba phương pháp phân tích amortized (cùng aggregate và accounting). Định nghĩa hàm Φ đo "nợ tích lũy" trong cấu trúc dữ liệu; amortized cost = chi phí thực + ΔΦ.

Bottleneck: Thao tác tốn nhiều nhất trong thuật toán, lặp lại nhiều nhất khi n tăng. Bước 3 trong framework 5 bước: tìm đúng bottleneck dẫn trực tiếp đến kỹ thuật tối ưu phù hợp.

Các bẫy hay gặp

Bẫy 1: tin Big-O thấp hơn là luôn nhanh hơn.

Insertion Sort O(n²) thường nhanh hơn Merge Sort O(n log n) với đoạn ngắn (cỡ vài chục phần tử) vì constant nhỏ hơn và cache-friendly. TimSort khai thác điều này. Kết luận từ Big-O chỉ đúng ở n đủ lớn. Với n nhỏ, đo thực tế.

Bẫy 2: nhầm amortized với average.

Average case phụ thuộc phân bố của input. Amortized là đảm bảo trên dãy thao tác xấu nhất, không cần giả định gì về input. QuickSort có average O(n log n) nhưng không có amortized O(n log n). ArrayList.add() có amortized O(1) — mạnh hơn average.

Bẫy 3: tăng stack size thay vì fix thuật toán.

Tăng giới hạn stack từ 512KB lên 8MB với 1.000 thread concurrent tốn 8GB bộ nhớ stack. Giải pháp đúng là chuyển sang iteration hoặc thêm giới hạn độ sâu tường minh — đặc biệt khi độ sâu phụ thuộc input bên ngoài.

Bẫy 4: dùng linked list vì "O(1) insert" mà quên chi phí duyệt.

list.add(index, value) trên linked list vẫn là O(n) tổng vì phải duyệt đến index. Lợi thế O(1) chỉ có khi đã có iterator trỏ sẵn vào vị trí cần insert. Trong đa số trường hợp, Deque mảng vòng tròn là lựa chọn tốt hơn cả ArrayList và LinkedList.

Bẫy 5: bỏ bước brute force khi "đã biết lời giải".

Không có kết quả đúng làm mốc (ground truth) thì không thể kiểm chứng khi bản tối ưu có bug. Brute force còn cho biết độ phức tạp xuất phát để xác nhận có cần tối ưu không. YAGNI: với n tối đa 1.000, O(n²) chạy trong ms — không cần phức tạp hóa.

Tự đánh giá

Bạn đã đạt module này nếu trả lời được:

• Giải thích được Big-O và phân biệt độ phức tạp lý thuyết với hành vi thực tế (cache, hằng số). Nếu chưa: đọc lại bài 01, Big-O từ bản chất mục 3 và 6.
• So sánh được ba phương pháp phân tích amortized (aggregate, accounting, potential) và áp dụng đúng cho dynamic array. Nếu chưa: đọc lại bài 03, Amortized analysis mục 3 và 4.
• Trace được đệ quy qua call stack và nhận diện điều kiện dừng, nguy cơ stack overflow. Nếu chưa: đọc lại bài 02, Recursion & call stack mục 2, 4 và 5.
• Chọn được chiến lược tối ưu (đổi không gian lấy thời gian, pre-size, đọc tuần tự cache-friendly) theo bài toán. Nếu chưa: đọc lại bài 04, Cache locality và bài 05, Framework mục 4.

Bài tiếp theo

Module 1 cho bạn ngôn ngữ và công cụ tư duy. Module 2 áp chúng vào các cấu trúc dữ liệu thực tế: mảng, stack, queue, deque, những building block có mặt ở mọi bài toán còn lại.

Cấu trúc tuyến tính bắt đầu bằng câu hỏi: khi nào dùng array, khi nào dùng ArrayList, khi nào cần Deque. Câu trả lời dựa đúng vào những gì bạn vừa học: amortized, cache locality, O(1) so với O(n).

Tài liệu mở rộng

• CLRS — Introduction to Algorithms, Chapters 3 & 17 — định nghĩa toán học đầy đủ Big-O và ba phương pháp amortized. Đọc Ch.3 trước, Ch.17 sau khi nắm aggregate method.
• Ulrich Drepper — What Every Programmer Should Know About Memory (2007) — 114 trang về cache hierarchy, TLB, prefetching. Đọc từ phần 3 (CPU cache) nếu bỏ qua phần giới thiệu phần cứng.
• Jon Bentley — Programming Pearls, Column 1 — nguyên mẫu của framework 5 bước: bài toán sort 10 triệu số với 1MB RAM, từ cách đơn giản đến tối ưu, từng bước.
• JVMS §2.6 — Frames — định nghĩa chính xác cấu trúc stack frame của JVM: local variable array, operand stack, frame data.

Bài tiếp theo: Cấu trúc tuyến tính: tổng quan