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

TL;DR: Module 1 trang bị 4 công cụ tư duy cốt lõi: Big-O làm ngôn ngữ đo lường, amortized giải thích hành vi trung bình trên dãy worst-case, call stack giải thích giới hạn đệ quy, cache locality giải thích khoảng cách giữa lý thuyết và thực tế. Bài này tổng kết toàn bộ, đánh dấu những pitfall hay gặp nhất, và kiểm tra xem bạn đã thực sự nắm 4 learning outcome của module chưa.

Đã đi qua những gì

Module 1 bắt đầu từ câu hỏi thực tế: hai đoạn code cùng đúng, cùng máy, nhưng một cái chạy 5ms còn cái kia 10 giây. Big-O là công cụ để trả lời câu hỏi đó — không phải đo thời gian tuyệt đối mà đo tốc độ tăng trưởng số bước khi n tăng.

Bài 01 dựng nền: bỏ constants vì ở n đủ lớn hạng bậc cao thống trị toàn bộ; ba ký hiệu O / Theta / Omega phục vụ các góc nhìn khác nhau; 7 complexity class từ O(1) đến O(n!) với khoảng cách tăng trưởng cơ bản.

Bài 02 khai thác một hệ quả ít được dạy: đệ quy trông gọn nhưng mỗi lời gọi push một frame lên thread stack 512KB–1MB. JVM không có TCO vì ràng buộc debugger và bytecode verifier. Ba pattern chuyển đổi — tail recursion thành while, tree recursion thành DP, general recursion thành Deque tường minh — giải quyết được phần lớn tình huống thực tế.

Bài 03 tháo gỡ nghịch lý: ArrayList.add() là O(1) amortized dù đôi khi tốn O(n) khi resize. Ba phương pháp phân tích (aggregate, accounting, potential) đều chứng minh tổng n lần add tốn dưới 2n phép — amortized O(1). Growth factor 1.5x được chọn vì tổng block cũ đủ cho allocator tái dùng (cần factor nhỏ hơn golden ratio ~1.618).

Bài 04 phá vỡ ảo giác "Big-O là đủ": cùng O(n) nhưng mảng số nguyên nhanh hơn linked list boxed 25 lần. L1 cache ~1ns, DRAM ~100ns — 100 lần chênh lệch. Cache line 64 byte nạp 16 int cùng lúc; hardware prefetcher dự đoán sequential access; pointer chasing vô hiệu hóa cả hai. Kết quả: data-oriented thinking quan trọng ngang algorithmic thinking.

Bài 05 đặt tất cả vào framework 5 bước: hiểu input/output → brute force → identify bottleneck → áp kỹ thuật → verify. Two Sum đi từ O(n²) brute force xuống O(n) hash map bằng cách nhận ra inner loop là linear search complement.

Bài 06 kiểm chứng bằng benchmark thực tế: findCommonElements với 1 triệu phần tử — naive timeout sau 8 giây, fast set hoàn thành trong 30ms. Curve thực tế xác nhận lý thuyết Big-O.

Cheat sheet

Glossary

Big-O (O) — Ký hiệu 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 trưởng asymptotic, không đo thời gian tuyệt đối.

Theta (Θ) — 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 (Ω) — 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ề distribution của input.

Stack frame — Khối bộ nhớ được cấp phát trên thread stack khi một hàm được gọi. Chứa biến cục bộ, tham số, return address, và frame pointer. Được 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ớ — 64 byte trên x86 và ARM hiện đại. Đọ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 pattern truy cập bộ nhớ và nạp trước dữ liệu vào cache. Hoạt động tốt với sequential access; vô hiệu với pointer chasing ngẫu nhiên.

Cache miss — Truy cập dữ liệu không có trong cache, buộc CPU fetch từ cấp bộ nhớ chậm hơn. L1 miss → L2 (~10ns); L2 miss → L3 (~30ns); L3 miss → DRAM (~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 invalidate cache line trên core của thread B, gây contention 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 cho phép allocator tái dùng block cũ.

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 = actual cost + ΔΦ.

Bottleneck — Operation 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: identify đúng bottleneck dẫn trực tiếp đến kỹ thuật tối ưu phù hợp.

Pitfall tổng hợp

Pitfall 1: Tin Big-O thấp hơn là luôn nhanh hơn.

Insertion Sort O(n²) nhanh hơn Merge Sort O(n log n) với n dưới 32 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ế.

Pitfall 2: Nhầm amortized với average.

Average case phụ thuộc distribution của input. Amortized là đảm bảo trên worst-case sequence — 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.

Pitfall 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 stack space. Giải pháp đúng là convert 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.

Pitfall 4: Dùng linked list vì "O(1) insert" quên traverse cost.

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.

Pitfall 5: Bỏ bước brute force khi "đã biết solution".

Không có ground truth → không thể verify khi optimized solution có bug. Brute force còn cho biết ceiling complexity để xác nhận 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.

Self-assessment

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.

What's next

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

Module 2 — 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 — và tại sao câu trả lời phụ thuộc vào đúng những gì bạn vừa học ở Module 1 (amortized, cache locality, O(1) vs 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 hardware intro.
• 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ừ naive đến optimal 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: Module 2 — Cấu trúc tuyến tính: tổng quan