Giải thích và đưa ví dụ về định lý chủ

Phương pháp chủ cung cấp một phương pháp kiểu “sách nấu ăn” để giải các phép truy toán có dạng
T(rì) – aT(rƯb)+ /(«), (45)
ở đó a> 1 và b> 1 là các hằng và /(n) là một hàm dương theo tiệm cạn. Phương pháp chủ yêu cầu phải nhó ba trường hợp, nhưng sau đó nghiệm của nhiều phép truy toán có thể được xác định khá dễ dàng, thường không cần đến giấy bút.
Phép truy toán (45) mô tả thời gian thực hiện của một thuật toán chia bài toán có kích cỡnthành abài toán con, mỗi bài có kích cỡn/h, ởđó avà blà các hằng dương, abài toán con được giải theo đệ quy, mỗi bài trong thời gian T{rưb).Hao phí của việc chia bài toán và tổ hợp các kết quả của các bài toán con được mô tả bằng hàm/(n).

(Nghĩa là, dùng hệký hiệu trong Đoạn 1.3.2,/(«) = D (rì)+ c (rt).)

Ví dụ, phép truy toán nảy sinh từ thủ tục MERGE-SORT có a = 2, b = 2, và f(rì) = 0(n).


Xét theo tính đúng đắn kỹ thuật, phép truy toán thực tế không được định nghĩa tốt bởi rưbcó thể không là một sốnguyên. Tuy nhiên, việc thay từng trong sô” a sốhạng T(n/b)bằng Tậ_rưbj)hoặc T§rưb\)sẽ không ảnh hưởng đến cách ứng xử tiệm cận của phép truy toán. (Ta sẽ chứng minh điều này trong đoạn sau.) Do đó, để tiện dụng, ta thường bỏ qua các hàm sàn và trần khi viết các phép truy toán chia để trị theo dạng này.

>>>>Xem thêm: Hãng hàng không Delta triển khai đường bay Seattle-Osaka

Định lý chủ
Phương pháp chủ tùy thuộc vào định lý sau.
Định lý 4.1 (Định lý chủ)
Cho a > 1 và h > 1 là các hằng, cho f (rì) là một hàm, và T(n)được định nghĩa trên các sô” nguyên không âm theo phép truy toán
Tịn) = aT(n/b) + fịn),
ở đó ta diễn dịch rưbtheo nghĩa \_n/bJ hoặc \n/b\Như vậy T(n) cóthể được định cận theo tiệm cận như sau.
1. Nếu/(n) = 0(n với một, hằng G> 0 nào đó, thi T(n)
– Q(rìữg”ư).
2. Nếu/(n) = 0(VogO, thìT(n)= 0(rtlovlg n).
3. Nếu f(n) = £2(/7,og/í’+ Ể) với một hằng G> 0 nào đó, và nếu a/ (n/b) <c f(rì)với một hằng c< 1 nào đó và tâ”t cảnđủ lớn, thìT(n)= 0(f(n))

>>>>Xem thêm: Xu hướng thời trang cho bé năm 2018

Trước khi áp dụng định lý chủ cho vài ví dụ, ta bỏ chút thời gian để tìm hiểu ý nghĩa của nó. Trong cá ba trường hợp, ta đang so sánh hàm J[n) với hàm n]ogb“. Theo trực giác, nghiệm cho phép truy toán được xác định bởi hàm lớn hơn trong sô” hai hàm. Như trong trường hợp 1, nếu hàm niữgt>a lớn hơn, nghiệm sẽ là T(n) = Q(nỊoiíbaỵNhư trong trường hợp 3, nếu hàm f[n) lớn hơn, nghiệm sẽ là T(n) – 0(/ (n)).

Như trong trường hợp 2, nếu hai hàm cùng kích cỡ, ta nhân với một thừa sô” lôga, và nghiệm sẽ là T(rì) “ 0(nlo-vlg n) – 0(/(rt)lg n).
Ngoài trực giác này, có vài chi tiết kỹ thuật cần được hiểu rõ. Trong trường hợp thứ nhất, không những/(n) phải nhỏ hơn nó còn phải nhỏ hơn theo đa thức. Nghĩa là, theo tiệm cận /(n) phải nhỏ hơn n[ogba một thừa sô” ìf với một hằng e> 0 nào đó. Trong trường hợp thứ ba, không những f(n)phải lớn hơn nlog^, nó còn phái lớn hơn theo đa thức và ngoài ra còn phải thỏa điều kiện “tính đều” [“regularity”] af(n/b) <cf(n).Điều kiện này được thỏa bởi hầu hết các hàm được định cận theo đa thức mà ta sẽ gặp.
Điều quan trọng là phải nhận thức rõ ba trường hợp này không bao hàm tất cả mọi khả năng cho/(n). Có một lỗ hổng giữa các trường hợp 1 và 2 khi /(n) nhỏ hơn nu,hư nhưng không nhỏ hơn theo đa thức. Cũng vậy, có một lỗ hổng giữa các trường hợp 2 và 3 khi/(n) lớn hơn rìogt>a nhưng không lớn hơn theo đa thức. Nếu hàm/(n) rơi vào một trong các lỗ hổng này, hoặc giả điều kiện tính đều trong trường hợp 3 không được duy trì, ta không thể dùng phương pháp chủ để giải quyết phép truy toán.
Dùng phương pháp chủ
Để dùng phương pháp chủ, chỉ việc xác định áp dụng trường hợp nào của định lý chủ (nếu có) và viết ra đáp án.

>>>>Xem thêm: Phương pháp lặp một phép truy toán đặc biệt

Để lấy ví dụ đầu tiên, hãy xét
T(n) = 9T{ĩƯ3) + n .
Với phép truy toán này, ta có a = 9, & = 3, /(n) = , và như vậy n)o7 = n]og 9 = 0(*2). Bởi/(n) = 0(nhs^€ịở đó e = 1, nên ta có thể áp dụng trường hợp 1 của định lý chủ và kết luận nghiệm là T(n) = 0(rt2).
Giờ đây hãy xét
T(n) = 7T2n/3) + 1,
ở đó a. = 1, b = 3/2,/(rt) = 1, và n’°7 = n‘°v = n° = 1. Trường hợp 2 áp dụng được, bởi / (n) = 0(n/o7’e) = 0(1), và như vậy nghiệm cho phép truy toán là T(n) = 0(lg n).
Với phép truy toán
T(n) = 3T(n/4) + nlg n ,
ta cóa = 3, b = 4,/(«) = n ỉg n, và n,og/ = nlog43 = ớ(n0 793). Do/(n) = Q(rtlog43+e) = 0(1) ở đó G ~ 0.2, nên trường hợp 3 áp dụng được nếu ta có thể chứng tỏ điều kiện tính đều áp dụng cho/(n). Với n đủ lớn, a f cn/b) = 3(n/4) \g(n/4)< (3/4)* lg n = c/(«) với C = 3/4. Bởi vậy, theo trường hợp 3, nghiệm cho phép truy toán là T(n) = 0(* lg *).
Phương pháp chủ không áp dụng cho phép truy toán