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
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Công thức tính diện tích xung quanh hình nón cụt, diện tích toàn phần hình nón cụt, thể tích hình nón cụt
-
Cách tính diện tích hình tròn và chu vi hình tròn
-
Công thức tính đường cao trong tam giác thường, cân, đều, vuông
-
Công thức tính diện tích hình quạt tròn
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
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
-
Cách viết mét vuông (m²), mét khối (m³) trên điện thoại, máy tính
Hôm qua -
Thơ vui về đàn ông và đàn bà
Hôm qua -
Hướng dẫn kích hoạt hoặc vô hiệu hóa bộ lọc SmartScreen trên Windows
Hôm qua -
Lệnh CS 1.1, mã Half Life trên máy tính
Hôm qua 3 -
Hướng dẫn tạo danh mục bảng biểu trong Word tự động
Hôm qua 3 -
Hentai là gì? Code hen là gì?
Hôm qua -
Cách kết nối máy in qua WiFi, cài máy in qua WiFi trên Windows 10/11
Hôm qua -
Corki DTCL mùa 7: Lên đồ, đội hình chuẩn Corki Pháo Thủ
2 ngày -
Cách sửa lỗi định dạng số khi dùng Mail Merge trong Word
Hôm qua -
Cách khôi phục danh bạ đã xóa trên iPhone
2 ngày