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) nhưng mảng nhanh hơn linked list 25 lần, và framework 5 bước biến bất kỳ bài toán mới nào thành approach có thể code được. Không cần kiến thức toán nâng cao — chỉ cần sẵn sàng đọ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 solution trên LeetCode, nhớ trick, á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ực sự không phải là thiếu trick — 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 trang bị đúng hai thứ đó:

• Big-O là ngôn ngữ chung. Khi tài liệu ghi O(log n), bạn biết chính xác điều đó có nghĩa 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 solution có complexity guarantee.

Ba bài ở giữa (đệ quy, amortized, cache) lấp đầy những khoảng trống mà dev thường gặp trong production nhưng ít ai giải thích đến nơi đến chốn:

• Tại sao recursive function 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 gấp 25 lần?

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 một tuyến logic: trước tiên học ngôn ngữ đo lường, sau đó học ba hiện tượng mà ngôn ngữ đó không nắm bắt được hoàn toàn, 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 khởi đầu bằng câu hỏi: tại 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 câu hỏi đó ở quy mô lớn. Bài giải thích tại sao bỏ constants vẫn đúng, phân biệt O / Theta / Omega, và 7 complexity class với pseudocode.

Bài 02 — Recursion & call stack đào sâu một nguy hiểm thực tế: đệ quy trông gọn về lý thuyết nhưng mỗi lời gọi push một stack frame lên thread stack có giới hạn. Tại sao JVM không có tail-call optimization? Khi nào nên chuyển sang iteration?

Bài 03 — Amortized analysis giải thích câu đố thoạt nghe 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) đều cho cùng kết quả — trung bình trên dãy thao tác worst-case, mỗi add() chỉ tốn hằng số.

Bài 04 — Memory & cache locality giải thích vì sao Big-O không đủ: cùng O(n) nhưng mảng số nguyên nhanh hơn danh sách liên kết 25 lần vì memory latency không nằm trong ký hiệu Big-O. Cache line 64 byte, hardware prefetcher, false sharing — những khái niệm này quyết định hiệu năng thực tế khi n đủ lớn.

Bài 05 — Framework giải bài tổng hợp tất cả thành quy trình 5 bước: hiểu input/output → brute force → identify bottleneck → áp kỹ thuật → verify. Áp vào bài Two Sum để thấy cách đi từ O(n²) xuống O(n) bằng suy nghĩ 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 curve tuyến tính vs bậc hai trên input triệu phần tử.

graph LR
    B01["Bài 01\nBig-O từ bản chất"]
    B02["Bài 02\nĐệ quy & call stack"]
    B03["Bài 03\nAmortized analysis"]
    B04["Bài 04\nCache locality"]
    B05["Bài 05\nFramework 5 bước"]
    B06["Bài 06\nMini-challenge"]
    RECAP["Bài 07\nTổng kết & cheat sheet"]

    B01 --> B03
    B01 --> B04
    B02 --> B05
    B03 --> B05
    B04 --> B05
    B05 --> B06
    B06 --> RECAP

Ba bài 01–04 xây nền tảng độc lập nhau (có thể đọc theo thứ tự bất kỳ nếu đã quen một phần). Bài 05 tổng hợp tất cả — nên đọc sau khi đã qua 01–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). Não nhớ quy trình tốt hơn khi tay đã làm một lầ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 không phải phụ lục — chúng là trọng tâm của module.

Self-check cuối mỗi bài là bắt buộc. Mỗi câu hỏi trong self-check đo một outcome cụ thể. Nếu không trả lời được câu nào, đọc lại phần tương ứng — đừ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í và tìm ra" trong 20 phút đó có giá trị học tập cao hơn đọc solution 5 phút.

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