Lesson 51 — Đánh đổi độ phức tạp

Ba module tương tác: Time vs Space (điểm hoà vốn precompute theo số query), Trade-off picker (chọn ngữ cảnh → gợi ý cấu trúc), và Break-even chart (đồ thị tổng chi phí của 2 cách theo số query).

Module 1 — Time vs Space: điểm hoà vốn precompute

Bài range-sum trên mảng kích thước n. So sánh Naive (mỗi query O(n), không tốn space) với Prefix sum (build O(n) một lần, mỗi query O(1), tốn O(n) space). Kéo số query và n để xem cách nào thắng — và vì sao.

Số query q = 100 (thang log: 1 → 10⁶)

Kích thước mảng n = 1000 (thang log: 10 → 10⁶)

Naive — tổng thao tác = q · n

—

Prefix — tổng thao tác = n (build) + q

—

Space phụ: Naive = O(1), Prefix = O(n). Prefix đổi space lấy time — và chỉ hời khi q đủ lớn để build cost được amortize.

Module 2 — Trade-off picker: ngữ cảnh → cấu trúc

Trả lời 5 câu hỏi về ngữ cảnh. Công cụ gợi ý đánh đổi/cấu trúc phù hợp theo khung quyết định (mục 11 trong README).

Bao nhiêu query?

Data có thay đổi không?

Có real-time deadline?

Memory budget?

Input có thù địch (adversarial)?

Gợi ý

—

Module 3 — Break-even chart

Đồ thị tổng chi phí theo số query q (với n cố định). Đường Naive = q·n (dốc, tuyến tính theo q). Đường Prefix = n + q (gần như phẳng — build cost cố định + 1/query). Giao điểm là điểm hoà vốn.

n = 100

Naive = q·n Prefix = n + q Điểm hoà vốn

—