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
1.137
★ 👨 1 Bình luận
Sắp xếp theo

Xóa Đăng nhập để viết
- Code NgầuThích · Phản hồi · 1 · 22:08 17/08
Tham khảo thêm
- Giải Pháp Quản Lý Mạng Từ Xa Cho Microsoft
- Những thủ thuật xử lý cột trong Microsoft Word
- Giải mã 6 màn ảo thuật thách thức mọi định luật vật lý trên đời
- Giải thuật là gì?
- Giải thuật tham lam (Greedy Algorithm)
- Giải thuật chia để trị (divide and conquer)
- Giải thuật qui hoạch động (Dynamic Programming)
Bài viết mới nhất
-
Google Classroom 1.0
-
11 sự thật về các chuyến bay dân dụng, biết để có chuyến đi thoải mái và an toàn hơn
-
Cách chỉnh sáng màn hình bằng ScreenTemperature giảm mỏi mắt
-
Cách sửa lỗi Windows 10 không thể khởi động do thiếu driver hệ thống, mã 0xc0000221
-
Cách chụp ảnh hiệu ứng bầm mắt trên Instagram
-
Đánh giá TP-Link Archer AX6000: Router WiFi nhanh như chớp
Cấu trúc dữ liệu và giải thuật
-
Công thức tính chu vi hình tứ giác, diện tích hình tứ giác
-
Công thức tính chu vi hình tam giác
-
Công thức tính chu vi hình thang: thường, vuông, cân
-
Cách giải phương trình bậc 2
-
Công thức tính diện tích hình bình hành, chu vi hình bình hành
-
Công thức tính diện tích xung quanh hình nón, diện tích toàn phần hình nón, thể tích hình nón