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

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

Tổng quan Module 1: Big-O, đệ quy & call stack, amortized analysis, cache locality, framework giải bài — nền tảng tư duy trước khi học bất kỳ thuật toán nào.

Độ phức tạp Big-O từ bản chất — Theta, Omega, amortized intro

Big-O đo tốc độ tăng trưởng khi n lớn — không phải thời gian tuyệt đối. Bài phân biệt O/Theta/Omega, 7 complexity class, và pitfall khiến O(n log n) chậm hơn O(n²).

Recursion & call stack — Khi đệ quy phá vỡ giới hạn ngăn xếp

Đệ quy ẩn nguy cơ tràn ngăn xếp trong production. Bài giải thích cơ chế call stack, lý do JVM thiếu TCO, và 3 pattern chuyển sang iteration an toàn.

Amortized analysis — ArrayList.add() O(1) dù đôi khi tốn O(n)

ArrayList.add() là O(1) amortized dù đôi khi tốn O(n). Bài giải thích 3 phương pháp phân tích amortized, lý do chọn growth factor 1.5x, và khi nào amortized lừa bạn.

Cache locality — Vì sao mảng nhanh hơn linked list 25 lần

Cùng O(n) nhưng mảng nhanh hơn linked list 25 lần. Bài giải thích CPU memory hierarchy, cache line, object layout, và khi nào Big-O không đủ để dự đoán hiệu năng thực tế.

Framework giải bài thuật toán — 5 bước biến brute force thành tối ưu

Framework 5 bước biến bài toán chưa từng gặp thành approach có thể code được: hiểu input, brute force, tìm bottleneck, áp kỹ thuật, verify — kèm complexity guarantee.

Mini-challenge — findCommonElements: naive vs optimized

Bài thực hành khép lại Module 1 — viết findCommonElements hai cách (nested loop vs hash set), đo benchmark, và nhận ra vì sao 8 giây xuống còn 30ms.

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

Tổng kết Module 1: cheat sheet concept, glossary 13 thuật ngữ, pitfall tổng hợp, self-assessment 4 outcome, và bước tiếp theo sang Module 2.