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.
Đị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))
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.
Để 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).
Chứng mỉnh định ỉý chủ
Đoạn này mô tả một phép chứng minh của định lý chủ (Định lý 4.1) dành cho bạn đọc cạp cấp hơn. Không cần phải hiểu rõ phép chứng minh để áp dụng định lý.
Phép chứng minh bao gồm hai phần. Phần đầu phân tích phép truy toán “chủ” (4.5), dưới giả thiết giản lược rằng T(n) chỉ được định nghĩa trên các lũy thừa chính xác của b> 1, nghĩa là, với n = 1, b, b2,…. Phần này cung cấp toàn bộ trực giác cần thiết để hiểu rõ tại sao định lý chủ lại đúng. Phần hai nêu cách mở rộng phép phân tích theo tất cả các số nguyên dương n và cách áp dụng kỹ thuật đơn thuần toán học cho bài toán điều quản cận dưới và cận trên.
Trong đoạn này, đôi lúc ta có phần lạm dụng hệ ký hiệu tiệm cận bằng cách dùng nó để mô tả cách ứng xử của các hàm chỉ được định nghĩa trên các lũy thừa chính xác của b. Chắc bạn còn nhớ, các phần định nghĩa của các hệ ký hiệu tiệm cận yêu cầu chứng minh các cận với tất cả các con số đủ lớn, chứ không chỉ với các lũy thừa của b. Bởi ta có thể tạo các hệ ký hiệu tiệm cận mới áp dụng cho tập hợp {£’; i = 0, 1, …}, thay vì các sô” nguyên không âm, lạm dụng này là không quan trọng.