Chia để trị (Divide and Conquer)
Thuật toán chia bài toán thành các bài toán con cùng loại, giải đệ quy, sau đó kết hợp kết quả.
function recursive(input size n):
if n < k:
Chia thành m bài toán con size n/p
Gọi đệ quy từng bài toán con
else:
Giải trực tiếp và trả về
Kết hợp kết quả
Định lý Master cơ bản
Dùng để tìm độ phức tạp thời gian dạng:
T(n) = f(n) + m·T(n/p)
Không áp dụng được khi: T(n) không đơn điệu (vd: sin n), f(n) không phải đa thức.
Định lý Master nâng cao (Advanced Master Theorem)
Xử lý truy hồi dạng:
T(n) = a·T(n/b) + Θ(nᵏ logᵖ n)
Trong đó: a > 0 (số bài toán con), b > 1 (hệ số chia size), k ≥ 0, p số thực.
Giải pháp
- Nếu a > bᵏ: T(n) = Θ(n^{log_b a})
- Nếu a = bᵏ:
- p > -1: T(n) = Θ(n^{log_b a} log^{p+1} n)
- p = -1: T(n) = Θ(n^{log_b a} log log n)
- p < -1: T(n) = Θ(n^{log_b a})
- Nếu a < bᵏ:
- p ≥ 0: T(n) = Θ(nᵏ logᵖ n)
- p < 0: T(n) = Θ(nᵏ)
Ví dụ ứng dụng
- Tìm kiếm nhị phân: T(n) = Θ(log n)
- Merge Sort: T(n) = Θ(n log n)