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
Bài toán ban đầu được chia thành a bài toán con có kích thước mỗi bài là n/b, chi phí để tổng hợp các bài toán con là f(n).
Ví dụ : Thuật toán sắp xếp trộn chia thành 2 bài toán con, kích thước n/2. Chi phí tổng hợp 2 bài toán con là O(n).
Đị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< b^k thì T(n) = O(n^k)
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
Theo Tutorialspoint
2.824
Bạn nên đọc
1 Bình luận
Sắp xếp theo
Xóa Đăng nhập để Gửi
- Code NgầuThích · Phản hồi · 1 · 17/08/20
Có thể bạn quan tâm
-
Cách tính mét khối (m³) gỗ, nước, bê tông...
-
Số chính phương là gì? Cách nhận biết và ví dụ chi tiết
-
Công thức tính thể tích khối lăng trụ đứng, hình lăng trụ
-
Công thức tính vận tốc, quãng đường, thời gian chính xác
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
-
Công thức tính diện tích tam giác: vuông, thường, cân, đều