Trong hướng dẫn này, bạn sẽ tìm hiểu định lý chính là gì và nó được sử dụng như thế nào để giải các quan hệ lặp lại.
Phương thức chính là một công thức để giải quyết các quan hệ lặp lại có dạng:
T (n) = aT (n / b) + f (n), trong đó, n = kích thước của đầu vào a = số bài toán con trong đệ quy n / b = kích thước của mỗi bài toán con. Tất cả các bài toán con được giả định có cùng kích thước. f (n) = chi phí của công việc được thực hiện bên ngoài lời gọi đệ quy, bao gồm chi phí chia bài toán và chi phí hợp nhất các giải pháp Ở đây, a ≧ 1 và b> 1 là các hằng số và f (n) là một tiệm cận dương chức năng.
Một hàm tiệm cận dương có nghĩa là với một giá trị đủ lớn của n, chúng ta có f(n)> 0.
Định lý tổng thể được sử dụng để tính toán độ phức tạp thời gian của các quan hệ lặp lại (thuật toán chia và chinh phục) một cách đơn giản và nhanh chóng.
Định lý Master
Nếu a ≧ 1và b> 1là hằng số và f(n)là một hàm tiệm cận dương, thì độ phức tạp thời gian của một quan hệ đệ quy được cho bởi
T (n) = aT (n / b) + f (n) trong đó T (n) có các đường tiệm cận sau: 1. Nếu f (n) = O (n log b a-ϵ ) thì T (n ) = Θ (n log b a ). 2. Nếu f (n) = Θ (n log b a ) thì T (n) = Θ (n log b a * log n). 3. Nếu f (n) = Ω (n log b a + ϵ ), thì T (n) = Θ (f (n)). ϵ> 0 là hằng số.
Mỗi điều kiện trên có thể được hiểu là:
- Nếu chi phí giải các bài toán con ở mỗi cấp độ tăng lên một hệ số nhất định, thì giá trị của
f(n)đa thức sẽ nhỏ hơn . Do đó, độ phức tạp về thời gian bị áp chế bởi chi phí của mức cuối cùng tức là.nlogb anlogb a - Nếu chi phí giải bài toán con ở mỗi cấp gần bằng nhau thì giá trị của
f(n)sẽ là . Do đó, độ phức tạp về thời gian sẽ nhân với tổng số cấp tức là.nlogb af(n)nlogb a * log n - Nếu chi phí giải các bài toán con ở mỗi cấp giảm đi một hệ số nhất định, giá trị của
f(n)sẽ trở thành đa thức lớn hơn . Do đó, độ phức tạp về thời gian bị áp chế bởi chi phí của .nlogb af(n)
Ví dụ đã giải quyết của Định lý Master
T (n) = 3T (n / 2) + n2 Ở đây, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1.58 <2 tức là. f (n) <n log b a + ϵ , trong đó, ϵ là hằng số. Trường hợp 3 ngụ ý ở đây. Do đó, T (n) = f (n) = Θ (n 2 )
Giới hạn của định lý chính
Không thể sử dụng định lý chính nếu:
- T (n) không đơn điệu. ví dụ.
T(n) = sin n f(n)không phải là một đa thức. ví dụ.f(n) = 2n- a không phải là hằng số. ví dụ.
a = 2n a < 1
