Hệ Thức Truy Hồi

Giải thức truy hồi

Trong bài này, chúng ta tìm hiểu một số cách giải công thức truy hồi mà chúng ta hay gặp trong phân tích thuật toán. Rất nhiều hệ thức truy hồi xuất hiện tỏng phân tích thuật toán có thể quy được về một trong 2 bài toán tổng quát sau:

Bài toán 1: Giải thức truy hồi:

trong đó a, b là cá hằng số dương.

và Bài toán 2: Giải hệ thức truy hồi:

trong đó ai,bi,i=1,…,k là các hằng số dương.

Trong bài này, chúng ta sẽ tìm hiểu 3 phương pháp giải. Mỗi phương pháp có ưu và nhược điểm riêng của nó. Ta bắt đầu với phương pháp đơn giản nhất.

1. Phương pháp đoán

Đây có lẽ là phương pháp mà chúng ta thường hay nghĩ tới khi bắt gặp một hệ thức truy hồi.

Nguyên lý: Dự đoán kết qủa và chứng minh bằng phương pháp quy nạp.

Theo nguyên lý, ta chỉ đơn giản giải hệ thức truy hồi bằng cách đoán nghiệm, thử chứng minh và đoán lại. Để minh hoạ, xét một vài ví dụ sau.

Ví dụ 1 Tìm công thức tổng quát của T(n) biết rằng: T(n)=2T(n−1)+1 với T(1)=1

Thử một vài giá trị đầu tiên, ta thấy: T(2)=3, T(3)=7, T(4)=15,…

Không khó để nhận ra 3 giá trị đầu thoả mãn quy luật: Do đó, ta có thể dự đoán: Chứng minh: Theo giả thiết quy nạp, ta có Do đó:

2. Định lý thợ

Định lý thợ (master theorem) là một công cụ giúp ta giải các hệ thức truy hồi có dạng trong bài toán 1. Định lý dài và khó nhớ và theo mình bạn đọc cũng không cần nhớ làm gì. Chỉ cần nhớ dạng bài toán mà định lý này có thể áp dụng để giải. Nếu có thể thì chỉ cần nhớ phương pháp chứng minh định lý.

Chứng minh: Chúng ta sử dụng phương pháp cây đệ quy. Cây đệ quy có nút gốc có giá trị f(n) và a nút con. Mỗi nút con của nút gốc sẽ là gốc của một cây cho hàm đệ quy T(n/b). Như vậy, ở độ sâu thứ i, giá trị của hàm của các nút là f(n/bi). Xem minh hoạ trong hình 1.

Hình 1: Minh hoạ cây đệ quy giải hệ thức truy hồi trong định lý thợ. Hình được cắt từ tài liệu tham khảo [1].

Sử dụng cây đệ quy ta suy ra: Ở đây L là độ sâu của cây đệ quy. Dễ thấy, L=logbn do mỗi lần đi xuống sâu thêm một mức của cây đệ quy, giá trị của n giảm đi b lần. Xét trường hợp:

• TH1: af(n/b)=f(n), ta có aif(n/bi)=f(n). Điều này có nghĩa là tổng giá trị tại mỗi mức của cây là f(n). Do cây có L mức, ta suy ra:
• TH2: af(n/b)=κf(n). Sử dụng phương pháp quy nạp, ta có Do đó, vì κ<1 ( xem thêm về geometric series).
• TH3: af(n/b)=Kf(n), sử dụng phương pháp quy nạp tương tự TH2, ta suy ra aif(n/bi)=Kif(n). Như vậy, Phương trình cuối là do K≤a vì af(n/b)≤af(n) do f(.) là một hàm đơn điệu tăng theo n khi n đủ lớn.

3. Phương pháp “Bom tấn”

Trong phần này chúng ta sẽ tìm hiểu một công cụ rất mạnh để giải công thức đệ quy có dạng trong bài toán 2. Phương pháp được đề xuất bởi Mohamad Akra và Louay Bazzi năm 1998. Với điều kiện k,ai,bi là các hằng số, lời giải của bài toán 2 có dạng như sau: Trong đó ρ thỏa mãn phương trình: Bạn đọc có thể tham khảo chứng minh của định lí này trong [2].

Ví dụ: Tìm tiệm cận của T(n) biết rằng T(n)=T(3n/4)+T(n/4)+n.

Lời giải: Áp dụng phương trình (2), ta tìm ρ thỏa mãn phương trình (3): (3/4)ρ+(1/4)ρ=1. Dễ thấy lời giải ở đây là ρ=1. Do đó, ta có: