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
Bạn nên đọc
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:

- Code NgầuThích · Phản hồi · 1 · 17/08/20

Cũ vẫn chất
-
Những dòng stt cô gái mạnh mẽ hay nhất
Hôm qua -
'Hack' tựa game khủng long của Google Chrome để chú T-Rex của bạn trở nên bất tử và max speed
Hôm qua 57 -
Cách tặng trang phục cho bạn bè trong Liên Quân
Hôm qua -
Cách bật báo biến động số dư trên Techcombank Mobile qua loa
Hôm qua -
Tổng hợp câu hỏi khó về tình yêu của con gái và bí kíp trả lời hoàn hảo cho các chàng
Hôm qua -
Cách tạo đường viền bảng trong Word
Hôm qua -
Những cách đơn giản để bắt chuyện với bất kỳ ai
Hôm qua -
Cách đổi số tiền thành chữ trong Excel, không cần add-in, hỗ trợ cả Excel 32-bit và 64-bit
Hôm qua 1 -
Remote Desktop Connection: Cách thiết lập chi tiết, 100% truy cập máy tính qua Internet thành công
Hôm qua 2 -
Hướng dẫn toàn tập chỉnh sửa ảnh trong GIMP
Hôm qua