Module 1 — Nền tảng: Cách đo và suy nghĩ về thuật toán

TL;DR: Module 1 xây nền tảng tư duy: Big-O đo tốc độ tăng trưởng (không phải thời gian tuyệt đối), amortized rải chi phí đắt ra nhiều bước rẻ, đệ quy chạy trên call stack có giới hạn, cache locality giải thích vì sao cùng O(n) mà mảng có thể nhanh hơn linked list hàng chục lần, và framework 5 bước giúp bạn biến một bài toán mới thành cách giải viết được thành code. Không cần toán nâng cao, chỉ cần đọc chậm và trace tay.

Vì sao module này tồn tại

Hầu hết dev học thuật toán theo kiểu: xem lời giải trên LeetCode, nhớ mẹo, áp vào bài tiếp theo. Cách này cho kết quả ngắn hạn nhưng gãy khi gặp bài chưa từng thấy.

Vấn đề thật không phải là thiếu mẹo, mà là thiếu ngôn ngữ chung để nói về hiệu năng và thiếu quy trình để tiếp cận bài mới.

Module này cho bạn đúng hai thứ đó:

• Big-O là ngôn ngữ chung. Khi tài liệu ghi O(log n), bạn biết nó nghĩa là gì ở quy mô triệu phần tử, không phải đoán mò.
• Framework 5 bước là quy trình. Gặp bài chưa từng thấy, bạn không bị kẹt: bạn có trình tự để đi từ "không biết bắt đầu từ đâu" đến một lời giải có độ phức tạp rõ ràng.

Ba bài ở giữa (đệ quy, amortized, cache) lấp những khoảng trống mà dev hay gặp ở production nhưng ít được giải thích kỹ:

• Tại sao hàm đệ quy tràn ngăn xếp dù trông hoàn toàn đúng?
• Tại sao tài liệu ghi O(1) nhưng đôi khi hàm lại tốn O(n)?
• Tại sao cùng O(n) mà một cách chạy nhanh hơn hàng chục lần?

Module không cần toán nâng cao, nhưng có giả định một thứ: bạn đã viết được code (biến, rẽ nhánh, vòng lặp, hàm) và đọc được một đoạn pseudocode ngắn mà không phải dừng lại đoán cú pháp. Nếu chưa, hoặc nếu chỗ vướng của bạn nằm ở lời giải gồm những bước nào chứ không phải ở chỗ đo lời giải nhanh chậm ra sao, thì Nhập môn Tư duy Lập trình dạy đúng phần đó trước: chạy chương trình bằng tay, bóc đề thành các bước, và chẩn đoán khi code sai, không ràng buộc vào ngôn ngữ nào.

Sau module này bạn sẽ

1. Explain 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ố)
2. Analyze chi phí amortized của thao tác qua aggregate / accounting / potential method
3. Trace đệ quy qua call stack và nhận diện điều kiện dừng, nguy cơ stack overflow
4. Choose 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

Lộ trình module

Module đi theo ba bước: học ngôn ngữ đo lường, học ba hiện tượng mà ngôn ngữ đó không nắm hết, rồi đặt tất cả vào quy trình thực hành.

Bài 01, Big-O từ bản chất, bắt đầu bằng câu hỏi: vì sao cùng kết quả đúng mà một hàm chạy 5ms còn hàm kia 10 giây? Big-O là công cụ để trả lời ở quy mô lớn. Bài giải thích vì sao bỏ constant vẫn đúng, phân biệt O / Theta / Omega, và 7 lớp độ phức tạp (complexity class) kèm pseudocode.

Bài 02, Recursion & call stack, nói về một rủi ro thật: đệ quy trông gọn nhưng mỗi lời gọi push một stack frame lên thread stack có giới hạn. Vì sao JVM không có tail-call optimization? Khi nào nên chuyển sang iteration?

Bài 03, Amortized analysis, giải một câu đố nghe có vẻ mâu thuẫn: ArrayList.add() được ghi là O(1) nhưng đôi khi tốn O(n). Ba phương pháp phân tích (aggregate, accounting, potential) cho cùng kết quả: trung bình trên cả dãy thao tác, mỗi add() chỉ tốn hằng số.

Bài 04, Memory & cache locality, cho thấy vì sao Big-O chưa đủ: cùng O(n) mà mảng số nguyên nhanh hơn linked list hàng chục lần, vì độ trễ bộ nhớ không nằm trong ký hiệu Big-O. Cache line 64 byte, hardware prefetcher, false sharing quyết định hiệu năng thật khi n đủ lớn.

Bài 05, Framework giải bài, gom tất cả thành quy trình 5 bước: hiểu input/output, brute force, tìm bottleneck, áp kỹ thuật, verify. Bài áp vào Two Sum để thấy cách đi từ O(n²) xuống O(n) có hệ thống.

Bài 06, Mini-challenge, là bài thực hành: viết findCommonElements hai cách, đo benchmark, và thấy tận mắt đường cong tuyến tính khác bậc hai thế nào khi n tăng dần.

Bốn bài 01 đến 04 khá độc lập nhau, nếu đã quen một phần thì đọc thứ tự nào cũng được. Bài 05 tổng hợp tất cả nên đọc sau 01 đến 04.

Cách học hiệu quả

Trace tay trước khi đọc giải thích. Mỗi bài có pseudocode: dừng lại, lấy giấy, chạy tay với input nhỏ (n = 4 hoặc 5). Tay làm một lần thì nhớ lâu hơn.

Đặt câu hỏi "tại sao" tại mỗi bước. Tại sao bỏ constant vẫn đúng? Tại sao 1.5x chứ không phải 2x? Tại sao mảng nhanh hơn? Những câu hỏi này là trọng tâm của module, không phải phụ lục.

Self-check cuối mỗi bài là bắt buộc. Mỗi câu hỏi trong self-check kiểm tra một mục tiêu cụ thể. Không trả lời được câu nào thì đọc lại phần đó, đừng bỏ qua vì "hiểu rồi".

Mini-challenge bài 06 phải tự làm trước khi xem gợi ý. Dành 20 phút thực sự làm trước khi mở callout gợi ý. Cảm giác "bí rồi tự tìm ra" trong 20 phút đó giúp nhớ lâu hơn đọc lời giải 5 phút.

Bài tiếp theo: Big-O từ bản chất