Phương pháp lặp một phép truy toán không yêu cầu ta suy đoán câu ưả lời, nhưng nó cổ thể yêu cầu nhiều đại sô”hơn phương pháp thay thế. Ý tưởng đó là mở rộng (lặp lại) phép ưuy toán và diễn tá nó dưới dạng một phép lâ”y tổng các số hạng chỉ lệ thuộc vào n và các điều kiện ban đầu. Như vậy, các kỹ thuật đánh giá các phép lây tổng có thể được dùng để cung câp các cận dựa trên nghiệm.
Để lây ví dụ, ta xem xét phép truy toán
T(n) = 3T(\_n /4_|) + n .
Ta lặp nó như sau:
T(n) = n + 37((U/4j)
= n + 3((L«/4j + 3r((Ln/16j))
= M + 3(Ln/4j + 3(Ln/16j + 3r(Ln/64j)))
= n + 3 L«/4j + 9 L«/l 6j + 277TL«/64J),
ở đó Hn/4j /4j = Ln/16J và LL«/1ốJ /4j = Ln/64j sinh ra từ đồng nhất thức (2.4).
Phải lặp phép truy toán đến đâu trước khi đạt đến một điều kiện biên? Số hạng thứi trong chuỗi là 3’Ltt/4’J. Phép lặp đụng n = 1 khi Lrư 4’J – 1 hoặc, tương đương, khi i vượt quá log4n. Bằng cách tiếp tục lặp lại cho đến điểm này và dùng cận Lrt/4’J <rư4′, ta phát hiện phép lấy tổng chứa một chuỗi cấp sô” nhân giảm:
Tịn)<n + 3rt/4 + 9n/16 + 27n/64 + … + 3to^’I0(l)
ỗ i(4)’+0(n’°*3)
i=0 V 4 /
= 4n + o(n)
= 0(n).
Ởđây, ta đã dùng đồng nhất thức (2.9) để kết luận rằng 3l0*4n = rtIog43, và ta đã dùng sự việc log43 < 1 để kết luận 0(«I(V) = o(n).
Phương pháp lặp thường dẫn đến khá nhiều đại sô”, và việc duy trì mọi thứ mạch lạc có thể là một thách thức. Điểm mâ”u chốt là tập trung vào hai tham sô”: sô” lần mà phép truy toán cần được lặp lại để đạt điều kiện biên, và tổng các sô” hạng nảy sinh từ mỗi cấp của tiến trình lặp lại. Đôi lúc, trong tiến trình lặp lại một phép truy toán, bạn có thể suy đoán nghiệm mà không cần giải quyết toàn bộ toán học. Như vậy, phép lặp có thể được loại bỏ để thay bằng phương pháp thay thế, thường yêu cầu ít đại sô” hơn.
Khi một phép truy toán chứa các hàm sàn và trần, toán học có thể trở nên đặc biệt phức tạp. Thường, ta nên mặc nhận rằng phép truy toán chỉ được định nghĩa dựa trên các lũy thừa chính xác của một con sô”. Trong ví dụ của chúng ta, nếu đã mặc nhận n = 4* với một sô” nguyên k nào đó, các hàm sàn có thể đã được bỏ qua để tiện dụng. Đáng tiếc, việc chứng minh cận T(n) = 0(n) vdi chỉ các lũy thừa chính xác của 4 xét về mặt kỹ thuật là một lạm dụng của hệ ký hiệu o. Các phần định nghĩa của 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 số nguyên đủ lớn, chứ không chỉ có các lũy thừa của 4. Ta sẽ thây trong Đoạn 4.3, với một lớp các phép truy toán lớn, chi tiết kỹ thuật này có thể khắc phục được. Bài toán 4-5 cũng đưa ra các điều kiện qua đó một phân tích với các lũy thừa chính xác của một sô”nguyên có thể mở rộng đến tất cả các sô” nguyên.
Các cây đệ quy
Cây đệ quy[recursion tree] là cách tiện dụng để hình dung nội dung xảy ra khi một phép truy toán được lặp lại, và nó có thể giúp tổ chức việc theo dõi diễn tiến đại số cần thiết để giải phép truy toán. Nó đặc biệt hữu ích khi phép truy toán mô tả một thuật toán chia để trị. Hình 4.1 có nêu tạo hàm của cây đệ quy với
T(n) = 2T(rƯ2) + n2.
Để tiện dụng, ta mặc nhận rằng n là một lũy thừa chính xác của 2. Phần (a) trong hình nêu T(n), mà trong phần (b) đã được mở rộng thành một cây tương đương biểu thị phép truy toán. Toán hạng n2 là gốc (hao phí tại cấp trên cùng của đệ quy), và hai cây con của gốc là hai phép truy toán T(n/2) nhỏ hơn. Phần (c) nêu tiến trình này được tiến hành một bước xa hơn bằng cách mở rộng T(n/2). Hao phí cho mỗi trong hai nút con [subnodes] tại cấp thứ hai của đệ quy lả (n/1)2. Ta tiếp tục mở rộng mỗi nút trong cây bằng cách tách thành các thành phần cấu tạo của nó như được xác định bởi phép truy toán, cho đến khi đạt được một điều kiện biên. Phần (d) nêu cây kết quả.
Giờ đây để đánh giá phếp truy toán, ta cộng các giá trị qua từng cấp của cây. cấp trên cùng có tổng giá trịn\ cấp thứ hai có giá trị(rứ2)2+(n/ 2Ỵ = n2/2, cấp thứ ba có giá trị (rt/4)2+(n/4)2+(tt/4)2+ (n/4)2 = n2/4, và vân vân. Bởi các giá trị giảm theo câp sô” nhân, nên tổng tối đa là một thừa sô” bâ”t biến hơn sô” hạng lớn nhâ”t (đầu tiên), và do đó nghiệm là
0(rt2).