Khi một thuật toán chứa một lệnh gọi đệ quy lên chinh nó, ta có thể dùng phép truy toán để mô tá thời gian thực hiện của nó. Một phép truy toán là một phương trình hoặc bất đẳng thức mô tả một hàm theo dạng giá trị của nó dựa trên các nhập liệu nhỏ hơn. Ví dụ, ta đã thấy trong Chương 1 rằng thời gian thực hiện trường hợp xấu nhất T(n) của thủ tục MERGE-SORT có thể được mô tả bằng phép truy toán mà nghiệm của nó được xác nhận là T(n) = Q(nlg/|).
Chương này cung cấp ba phương pháp để giải quyết các phép truy toán—nghĩa là, để có được các cận tiệm cận “0” hoặc “ỡ” dựa trên nghiệm. Trong phương pháp thay thế, ta suy đoán một cận rồi dùng phép quy nạp toán học để chứng minh sự suy đoán của ta là đúng. Phương pháp ỉặp chuyển đổi phép truy toán thành một phép lấy tổng rồi dựa trên các kỹ thuật định cận các phép lấy tổng để giải quyết phép truy toán. Phương pháp chủ cung cấp các biên cho các phép truy toán theo dạng
T(n) = aT(rứb) +f(n\ d đó a > 1, b> 1, vầf(n) là một hàm đã cho; ta cần nhớ ba trường hợp này; và một khi đã nhớ, việc xác định các cận tiệm cận cho nhiều phép truy toán đơn giản sẽ trở nên dễ dàng.
Tiểu tiết kỹ thuật
Trong thực tế, ta không đểý đến một số chi tiết kỷ thuật nhất định khi phát biểu và giải quyết các phép truy toán. Một ví dụ tốt về một chi tiết thường được xem nhẹ đó là giả thiết về các đối số số nguyên cho các hàm. Thông thường, thời gian thực hiện T(n) của một thuật toán chỉ được định nghĩa khi n là một số nguyên, bởi với hầu hết các thuật toán, kích cỡ nhập liệu luôn là một số nguyên. Ví dụ, phép truy toán mô tả thời gian thực hiện trường hợp xấu nhất của MERGE-SORT thực sự là
f0( 1) nếu n= ],
T(n)=I 2T{\nlĩ\) + 2T(lnl2\) + 0(n) nếu n> 1, (4.2)
Các điều kiện biên[boundary conditions] biểu thị cho một lớp chi tiết khác mà ta thường bỏ qua. Bởi thời gian thực hiện của một thuật toán trên một nhập liệu có kích cỡ bất biến là một hằng, các phép truy toán nảy sinh từ các thời gian thực hiện của các thuật toán thường có T(n) = 0(1) với n đủ nhỏ. Kết quả là, để tiện dụng, ta thường bỏ qua các phát biểu về các điều kiện biên của các phép truy toán và mặc nhận rằng T(n) là bâ’t biến với n nhố. Ví dụ, ta thường phát biểu phép truy toán(3.1) dưới dạng T(n) = 2T(n/2) + 0(n), (4.3) mà không rõ rệt gán các giá trị cho n nhỏ. sở dĩ như vậy là vì mặc dù việc thay đổi giá trị của 7(1) sẽ làm thay đổi nghiệm đốì với phép truy toán, song nghiệm thường không thay đổi theo nhiều hơn một thừa sô” bâ”t biến, do đó cấp tăng trưởng là không thay đổi.
Khi phát biểu và giải quyết các phép truy toán, ta thường bỏ qua cận dưới, cận trên, và các điều kiện biên. Ta tiến tới mà không cần các tiểu tiết này và về sau xác định xem chúng có ý nghĩa hay không. Thường thì không, song điều quan trọng là phải biết khi nào chúng có ý nghĩa. Kinh nghiệm sẽ giúp ta điều đó, và vì thế một số định lý cũng phát biểu rằng các chi tiết này không ảnh hưởng đến các cận tiệm cận của nhiều phép truy toán mà ta gặp trong khi phân tích các thuật toán (xem Định lý 4.1 và Bài toán 4-5).
Tuy nhiên, trong chương này, ta sẽ đề cập vài chi tiết đó để cho thây các điểm tế nhị của các phương pháp giải quyết phép truy toán.
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).