Lesson 05 — Brute-force → Tối ưu hóa

3 module tương tác để cảm nhận tư duy tối ưu: (1) Two Sum brute O(n²) vs hash O(n) chạy song song, đếm thao tác; (2) picker ánh xạ "mùi" phí phạm → kỹ thuật; (3) benchmark kéo slider n xem chênh lệch thao tác giãn ra theo n².

1. Two Sum — Brute O(n²) vs Hash O(n)

Mảng (cách nhau dấu phẩy): target:

Brute-force O(n²) — thử mọi cặp

Phép so sánh: 0

Hash O(n) — một pass

seen = {}

Bước: 0

Brute duyệt mọi cặp (i, j) tới khi cộng ra target. Hash với mỗi v hỏi map "đã thấy target − v chưa?" — tra O(1). Bấm "Chạy song song" để so số thao tác.

2. Optimization picker — chọn "mùi" → gợi ý kỹ thuật

Click một "mùi" phí phạm bạn thấy trong code brute-force để xem kỹ thuật chữa tương ứng:

Tính lại cùng giá trị

for r {{ sum=0; for k=l..r sum+=a[k] }}

Tìm kiếm lặp trong list

for i { for j if a[j]==x }

Duyệt mọi cặp trên dữ liệu sorted/đơn điệu

for i { for j > i ... } // a đã sort

Đệ quy lồng nhau có overlap

f(n) = f(n-1) + f(n-2) // gọi lại

3. Benchmark — Brute O(n²) vs Optimal O(n)

n = 20

Brute O(n²)
≈ n(n−1)/2

Optimal O(n)
= n

Kéo slider để thấy: brute giãn theo n² (cao vọt), optimal chỉ tuyến tính. Ở n nhỏ chênh lệch không đáng kể (mục 8 README: brute là đủ); n lớn thì cách biệt bùng nổ.