Chuyển tới nội dung chính

Quan hệ truy hồi & Định lý thợ

Bạn sẽ học được gì

Làm sao tính Big-O của một thuật toán đệ quy/chia để trị? Bài (nâng cao) này giới thiệu quan hệ truy hồi và Định lý thợ (Master Theorem) — một công thức "tra bảng" cho ra Big-O nhanh mà không cần lần từng tầng.

1. Quan hệ truy hồi là gì?​

Với thuật toán đệ quy, thời gian chạy của bài cỡ n được viết theo thời gian của các bài con nhỏ hơn. Đó là quan hệ truy hồi. Ví dụ merge sort:

T(n) = 2·T(n/2) + n
       ▲    ▲      ▲
       │    │      └── việc làm THÊM mỗi tầng (trộn 2 nửa): tốn n
       │    └── mỗi bài con cỡ n/2 (chia đôi)
       └── chia thành 2 bài con

Đọc là: "giải bài cỡ n = giải 2 bài cỡ n/2, cộng thêm n việc để trộn".

2. Định lý thợ — công thức tra nhanh​

Cho quan hệ dạng chuẩn:

T(n) = a · T(n / b) + f(n)
  • a = số bài con mỗi tầng.
  • b = mỗi bài con nhỏ đi bao nhiêu lần.
  • f(n) = việc làm thêm mỗi tầng (ngoài các lời gọi đệ quy).

So sánh f(n) với n^(log_b a) (gọi tắt là mốc). Có 3 trường hợp:

Trường hợpĐiều kiệnKết quả
1f(n) nhỏ hơn mốcT(n) = Θ(n^(log_b a))
2f(n) bằng mốcT(n) = Θ(n^(log_b a) · log n)
3f(n) lớn hơn mốcT(n) = Θ(f(n))

Nghe khô khan — nhưng áp vào ví dụ thì rõ ngay.

3. Áp dụng: ba thuật toán quen thuộc​

Merge sort: T(n) = 2·T(n/2) + n. Ở đây a=2, b=2 → mốc n^(log₂2) = n¹ = n. f(n)=n bằng mốc → Trường hợp 2 → Θ(n log n). ✅ Đúng như ta biết.

Binary search: T(n) = 1·T(n/2) + 1. a=1, b=2 → mốc n^(log₂1) = n⁰ = 1. f(n)=1 bằng mốc → Trường hợp 2 → Θ(1 · log n) = Θ(log n). ✅

Duyệt cây nhị phân: T(n) = 2·T(n/2) + 1. a=2, b=2 → mốc n. f(n)=1 nhỏ hơn mốc → Trường hợp 1 → Θ(n). ✅ (thăm mỗi nút một lần).

4. Kiểm chứng bằng số: merge sort ~ n log n​

Đếm số phép trộn của merge sort và so với n log₂ n. Bấm Run:

Đang tải trình chạy code…

Số phép trộn bám sát n·log₂n → khớp dự đoán Θ(n log n) của Định lý thợ.

5. Khi nào KHÔNG dùng được Định lý thợ?​

Định lý thợ chỉ áp cho dạng chuẩn a·T(n/b) + f(n) với các bài con cùng cỡ. Không áp được khi:

  • Bài con khác cỡ nhau (vd T(n-1) + T(n-2) của Fibonacci).
  • f(n) dạng kỳ lạ không so được với mốc.

Những lúc đó dùng cách khác (vẽ cây đệ quy, hoặc phân tích trực tiếp). Với DSA cơ bản, Định lý thợ phủ được đa số trường hợp chia để trị.

6. Mẫu nhận diện​

  • Thấy thuật toán chia đôi rồi gọi đệ quy → viết T(n) = a·T(n/b) + f(n) rồi tra 3 trường hợp.
  • Chia đôi + trộn tuyến tính (f(n)=n, a=b=2) → n log n.
  • Chia đôi + chỉ đi một nửa (a=1) → log n.

7. 🎮 Trò chơi: Áp dụng Định lý thợ​

🎮 Định lý thợCâu 1/4· Điểm 0· 🔥 0

Với T(n)=a·T(n/b)+f(n): so f(n) với mốc n^(log_b a). Bằng nhau → thêm log n.

Big-O? (merge sort)

T(n) = 2·T(n/2) + n

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Trong T(n) = a·T(n/b) + f(n), "a" là gì?
2. Merge sort: T(n)=2T(n/2)+n cho ra?
3. Định lý thợ dùng để?

9. Hoàn thành — XONG TRỤ 1! 🎉​

…

🎉 Bạn đã hoàn thành Trụ 1 — Nền tảng: tư duy thuật toán, độ phức tạp (Big-O) và đệ quy. Đây là nền móng cho mọi thứ phía sau. Tiếp theo: Trụ 2 — Cấu trúc dữ liệu.