Giải thuật Định lý thợ (Master Theorem)

Giải thuật Định lý thợ (Master Theorem) là gì ?

Chúng ta sử dụng Định lý thợ (Master Theorem) để giải các công thức đệ quy dạng sau một cách hiệu quả :

T(n) =aT(n/b) + c.n^k trong đó a>=1 , b>1

Định lý thợ

a>=1, b>1, c, k là các hằng số. T(n) định nghĩa đệ quy trên các tham số không âm

T(n) = aT(n/b) + c.n^k + Nếu a> b^k thì T(n) =O(n^ (logab)) + Nếu a= b^k thì T(n)=O(n^k.lgn) + Nếu a

Chú ý: Không phải trường hợp nào cũng áp dụng được định lý thợ

VD : T(n) = 2T(n/2) +nlogn a =2, b =2, nhưng không xác định được số nguyên k