Đáng tiếc, không có một cách chung nào để suy đoán các nghiệm đúng đắn cho các phép truy toán. Việc suy đoán một nghiệm đòi hỏi sự kinh nghiệm và, đôi lúc, cả óc sáng tạo. Tuy nhiên, may thay, có vài phép phỏng đoán [heuristics] có thể giúp ta trở thành người suy đoán tốt.
Nếu một phép truy toán tương tự như đã gặp ưước đó, thì việc suy đoán một nghiệm tương tự là hợp lý. Để lấy ví dụ, ta xem xét phép truy toán
T(n) = mln/l} + 17 ) + n,
nó có vẻ khó bởi “17″ trong đối số được cộng vào T bên phía phải. Tuy nhiên, theo trực giác, số hạng bổ sung này thực chất không thể ánh hưởng đến nghiệm đối với phép truy toán. Khi n lớn, sự khác biệt giữaTin/ll) và T(ln/2]+ 17) không lớn đến như vậy: cả hai đều cắt đôi n gần đều nhau. Kết quả, ta đưa ra suy đoán rằng T(n) = 0(n\gn), mà bạn có thể xác minh là đúng bằng phương pháp thay thế (xem Bài tập 4.1- 5).
Một cách khác để đưa ra một suy đoán tốt đó là chứng minh các cận trên và cận dưới “lơi” [loose] trên phép truy toán rồi thu nhỏ miền bất định. Ví dụ, có thể bắt đầu bằng một cận dưới T(n) = £2(rc) cho phép truy toán (4.4), bởi ta có số hạng n trong phép truy toán, và có thể chứng minh cận trên ban đầu là T(n) – Oịn2). Như vậy, có thể từ từ hạ thấp cận trên và nâng cận dưới lên cho đến khi hội tụ trên nghiệm đúng, sát theo tiệm cận là T(n) = 0(fllg rì).
Các điểm tinh tế
Có những lúc ở đó có thể suy đoán đúng đắn tại một cận tiệm cận cho nghiệm của một phép truy toán, nhưng không hiểu làm sao toán học dường như có gì trục trặc trong phương pháp quy nạp. Thông thường, vấn đề đó là giả thiết quy nạp không đủ mạnh để chứng minh cận chi tiết [detailed bound]. Khi gặp phải một dạng khó khăn đột xuất như vậy, việc xem lại phép suy đoán bằng cách trừ một số hạng cấp thấp thường cho phép khắc phục vấn đề toán học.
Hãy xem xét phép truy toán Tịn) = f(Ln/2j) + r<fn/2l) + 1 .
Ta suy đoán rằng nghiệm là O(n), và gắng chứng tỏT(n)<cn với một chọn lựa thích hợp cho hằng c. Thay thế suy đoán trong phép truy toán, ta có
T(n)Ln/2j < c L«/2j + cr«/2~l + 1
= cn + 1 ,
điều này không hàm ýT(n) < cn với bất kỳ chọn lựa nào của c. Nó đang lôi kéo ta thử một suy đoán lớn hơn, giả sửT(n) = 0(n2ỵ có thể được tạo để làm việc, nhưng trên thực tế, suy đoán của ta đối với nghiệm T(n) = O(n) là đúng đắn. Tuy nhiên, để chứng tỏ điều này, ta phải tạo một giá thuyết quy nạp mạnh hơn.
Về trực giác, suy đoán của ta là gần đúng: chỉ để hụt hằng 1, một số hạng câp thâp. Tuy vậy, phép quy nạp toán học sẽ không làm việc trừ phi ta chứng minh dạng thức chính xác của giả thuyết quy nạp. Để khắc phục khó khăn này, ta trừ một số hạng cấp thấp ra khỏi suy đoán trên đây. Suy đoán mới sẽ là T(n) < cn – byở đó b> 0 là bất biến. Giờ đây ta có
T(n) < (cU/2J – b) + (c (\n!2] – b) + l
= cn – 2b + 1
< cn-b ,
miễn là b > 1. Cũng như trước, hằng c phải được chọn đủ lớn để điều quản các điều kiện biên.
Đa sổ” người nhận thây ý tưởng trừ một số hạng câ”p thâ”p trái với trực giác. Xét cho cùng, nếu toán học không giải được, phái chăng ta không được gia tăng sự suy đoán của mình? Điểm mâu chốt để hiểu bước này là nhớ kỹ ta đang dùng phép quy nạp toán học: có thể chứng minh một nội dung mạnh hơn với một giá trị đã cho bằng cách mặc nhận một nội dung mạnh hơn với các giá trị nhỏ hơn.
Tránh các chỗ bẫy
Sẽ dễ dàng gặp lỗi khi dùng hệ ký hiệu tiệm cận. Ví dụ, trong phép truy toán (4.4) ta có thể chứng minh sai T{n) = O(n) bằng cách suy đoán T(n) < cn
rồi biện luận
T(n) < 2(c LH/2_|) + n
< cn + n
= O(n), <= sai ỉỉ
bởi c là một hằng. Lỗi đó là ta chưa chứng minh dạng chính xác của giả thuyết quy nạp, nghĩa là, T(n) < cn.
Thay đổi các biên
Đôi lúc, chỉ cần một điều tác đại sô” nhỏ là có thể khiến một phép truy toán vô danh ưở thành tương tự như đã gặp trên đây. Để lấy ví dụ, hãy xem xét phép truy toán
T(n) = 2T(L^J) + lg n,
NÓ có vẻ khó. Tuy nhiên, có thể đơn giản hóa phép truy toán này bằng cách thay đổi các biến. Để tiện dụng, ta sẽ không quan tâm về việc làm tròn các giá trị, như Vn, sẽ là các sô” nguyên. Gọi tên lại m = ĩg n cho ra
T(2m) = 2T(2ma) + m .
Giờ đây có thể đặt tên lại S(m) = T(2m) để tạo phép truy toán mới S(m) = 2S(mỉ2) + m ,
trông rất giông phép truy toán (4.4) và có cùng nghiệm: S{m) – 0(m lg m). Thay đổi ngược từS(m) thành T(n\ ta có T(n) – T(2m) = S(m) = 0(m\g m) = OiIg rtlglg n).
Bài tập
4.1- 1
Chứng tỏ nghiệm của T(n) – T( ĩn/ĩ]) + 1 là ỡ(lg n).
4.1- 2
Chứng tỏ nghiệm của T(n) ~ 2T(|_rt/2j ) + n ]ầ Q(nlg n). Kết luận nghiệm là 0(nlg n).
4.1- 3
Chứng tỏ bằng cách lộp một giả thuyết quy nạp khác, ta có thể khắc phục khó khăn bằng điều kiện biên 7(1) = 1 với phép truy toán (4.4) mà không điều chỉnh các điều kiện biên với phép chứng minh quy nạp.
4.1- 4
Chứng tỏ&(n lg n) là nghiệm cho phép ưuy toán “chính xác” (4.2) để sắp xếp trộn.
4.1- 5
Chứng tỏ nghiệm cho T(n) = 27(Lrt/2j + 17) + n là 0(n\g n).
4.1- 6
Giải phép ưuy toán T(n) – 27(V/ĩ) + 1 bằng cách thay đổi các biến. Đừng quan tâm về việc các giá trị có phải là tích phân hay không.