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.
Phương pháp thay thê”
Phương pháp thay thế để giải quyết các phép truy toán thường liên quan đên việc suy đoán dạng thức của nghiệm rồi dùng phép quy nạp toán học để tìm ra các hằng và chứng tỏ nghiệm làm việc. Tên gọi xuâ”t xứ từ việc dùng đáp án suy đoán thay cho hàm khi giả thuyết quy nạp được áp dụng cho các giá trị nhỏ hơn. Tuy phương pháp này mạnh, song hiển nhiên chỉ có thể áp dụng nó trong các trường hợp dễ dàng suy đoán dạng thức của đáp án.
Có thể dùng phương pháp thay thế để thiết lập các cận trên hoặc cận dưới cho một phép truy toán. Để lấy ví dụ, hãy j?ầc địnlvnột cận trên cho phép truy toán
T(n) = 27TU/2J) + n ,
nó tương tự như các phép truy toán (4.2) và (4.3). Ta suy đoán nghiệm là T(n) = 0(n lg n). Phương pháp của chúng ta là chứng minh rằng T{n) < cn\g n với một chọn lựa thích hợp cho hằng c > 0. Để bắt đầu, ta giả định cận này áp đụng cho Lrt/2_|, nghĩa là, 7(Lrt/2_|) <c L«/2j lg( \_nỉ2_|). Thay vào phép truy toán cho ra
T(n) < 2(cU/2jlg(L«/2j)) + «
< cn lg(rt/2) + n
= cnlgn – cnlg2 + n
= cnìgn – cn + n
< cnlg n ,
ở đổ bước cuối có thể áp dụng miễn là c> 1.
Phương pháp quy nạp toán học giờ đây yêu cầu ta chứng tỏ nghiệm áp dụng cho các điều kiện biên. Nghĩa là, ta phải chứng tỏ có thể chọn hằng c đủ lớn sao cho cận T(n) < cn Ig n cũng áp dụng cho các điều kiện biên. Đôi lúc yêu cầu này có thể dẫn đến các vấn đề. Để biện luận, ta giả sử T(l) = 1 là điều kiện biên duy nhất của phép truy toán. Đáng tiếc, như vậy ta không thể chọn c đủ lớn, bởi T(Ị) < c 1 lg 1 – 0.
Có thể dễ dàng khắc phục khó khăn trong việc chứng minh một giả thiết quy nạp cho một điều kiện biên cụ thể. Ta vận dụng sự việc hệ ký hiệu tiệm cận chỉ yêu cầu chứng minh T(n) <cn\gn với n> nồ,ở đó nQ là một hằng. Điểm mấu chốt đó là không xem xét điều kiện biên khó 7(1) = 1 trong phép chứng minh quy nạp và gộp n = 2 và n = 3 dưới dạng một phần của các điều kiện biên cho phép chứng minh. Ta có thể áp đặt 7(2) và 7(3) làm các điều kiện biên cho phép chứng minh quy nạp bởi vđi n > 3, phép truy toán không trực tiếp lệ thuộc vào 7 (1). Từ phép truy toán, ta suy ra 7(2) = 4 và 7(3) = 5. Giờ đây để hoàn tất phép chứng minh quy nạp 7(n) <cn lg n với một c > 2 nào đó, ta chọn c đủ lớn sao cho 7(2) < c2 Ig 2 và 7(3) < c3 Ig 3. Và như vậy, một chọn lựa c > 2 bất kỳ đều đủ. Với hầu hết các phép truy toán sẽ được xem xét ở đây, ta chỉ việc mở rộng các điều kiện biên để khiến giả thiết quy nạp làm việc với n nhỏ.
Tham khảo ngay thiết kế menu đồ uống chuyên nghiệp và uy tín từ Designer Group, giúp bạn tạo một menu thức uống ấn tượng với khách hàng.