Hi mọi người, tiếp theo series mình sẽ trình bày về giải thuật Divide and Conquer(Chia để trị)
1.22 Master Theorem for Divide and Conquer Recurrences
Tất cả các thuật toán Divide and Conquer (Mình sẽ thảo luận chi tiết trong chương Divide and Conquer) chia bài toán thành các bài toán con, mỗi bài toán là một phần của bài toán ban đầu, sau đó thực hiện một số công việc bổ sung để tính ra câu trả lời cuối cùng.
Ví dụ, thuật toán Merge sort (Mình sẽ trình bày kĩ hơn ở chương Sort) hoạt động trên hai bài toán con, mỗi bài toán nhỏ bằng một nửa kích thước của bài toán ban đầu T(n/2), và sau đó thực hiện thêm O(n) công việc để hợp nhất.
=> Điều này đưa ra phương trình tính running time:
Định lý sau có thể được sử dụng để xác định thời gian chạy của các divide and conquer.
Đối với một chương trình (thuật toán) đã cho, trước tiên chúng ta cố gắng tìm mối quan hệ lặp lại cho vấn đề.
Nếu sự lặp lại có dạng như dưới đây thì chúng ta có thể trực tiếp đưa ra câu trả lời mà không cần giải quyết hoàn toàn.
với a ≥ 1, b > 1, k ≥ 0 và b là 1 số thực thì:
- Nếu a > b^k
- Nếu a = b^k
- a. Nếu p > –1
- b. Nếu p = –1
- c. Nếu p < –1
- Nếu a < b^k
- a. Nếu p ≥ 0
- b. Nếu p < 0
Định lý quả thật phức tạp, mình xin phép chỉ dừng ở mức độ sử dụng định lý và áp dụng, các bạn nếu như có đam mê sâu hơn về toán muốn chứng minh định lý có thể tham khảo link sau(hoặc gg search thêm giúp mình nhé 😁):
[https://www.cs.purdue.edu/homes/spa/papers/jacm-divide.pdf]
1.23 Divide and Conquer Master Theorem: Problems & Solutions
Đối với mỗi problem sau đây, đưa ra một biểu thức cho thời gian chạy T(n) nếu nó có thể được giải quyết bằng Master Theorem.
Nếu không, chỉ ra rằng Master Theorem không áp dụng.
Problem-1
T(n) = 3T (n/2) + n^2
Solution: Các bạn tìm từ biểu thức các biến a, b, k, p rồi kiểm tra xem nó thuộc trường hợp nào trong Master Theorem, các bài sau các bạn áp dụng tương tự nhé.
Giải thích chi tiết:
Ta có a=3, b=2, k=2, p=0(Vì n^2 = n^2 * 1 = n^2 * (1 biểu thức bất kỳ)^0 )
⇒ 3 < 2^2 và p = 0 ⇒ T(n) = Θ(n^2) (Master Theorem Case 3.a)
Problem-2
T(n) = 4T (n/2) + n^2
Solution: T(n) = 4T (n/2) + n^2 ⇒ T (n) = Θ(n^2 * logn) (Master Theorem Case 2.a)
Problem-3
T(n) = T(n/2) + n 2
Solution: T(n) = T(n/2) + n^2 ⇒ Θ(n^2) (Master Theorem Case 3.a)
Problem-4
T(n) = 2^n * T(n/2) + n^n
Solution: T(n) = 2^n T(n/2) + n n ⇒ Không áp dụng vì a không phải 1 hằng số)
Problem-5
T(n) = 16T(n/4) + n
Solution: T(n) = 16T (n/4) + n ⇒ T(n) = Θ(n^2) (Master Theorem Case 1)
Từ đây các kí hiệu số mũ trong hàm log hơi khó biểu diễn trên viblo nên mình xin phép dùng ảnh
Bài viết này hơi nặng về toán, nó là lý thuyết tổng quát cho giải thuật chia để trị. Ở các chương sau khi có các bài toán cụ thể hơn sẽ áp dụng các lý thuyết này để tính được độ phức tạp của giải thuật 😁
Nguồn: viblo.asia