Phương pháp giải hệ thức truy hồi -- Recurrence Relation

Công thức truy hồi là một công thức tính giá trị của hàm phụ thuộc vào chính hàm đó. Một vài gía trị đầu tiên của hàm thường được cho trước gọi là base case. Ví dụ công thức truy hồi tính gía trị dãy số Fibonacci:

T(n) = T(n-1) + T(n-2) \qquad \qquad T(1) = T(2) = 1

Trong bài này, chúng ta sẽ nghiên cứu các cách giải hệ thức truy hồi. Mục tiêu của chúng ta là giải bài toán sau:
 

Problem 1: giải hệ thức truy hồi:

T(n) = aT(\frac{n}{b}) + f(n)

 

Problem 2: giải hệ thức truy hồi:

T(n) = \sum_{i=1}^k a_iT(\frac{n}{b_i}) + f(n)

 

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

Example 1 (Bài toán tháp Hà Nội):

T(n) = 2T(n-1) + 1 \qquad \qquad 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, \ldots

Dự đoán: T(n) = 2^n -1
Chứng minh:

T(n) = 2T(n-1) + 1 = 2(2^{n-1}-1) + 1 = 2^n -1

Bây giờ chúng ta thử áp dụng cho bài toán khó hơn

Example 2:

T(n) = \sqrt{n}T(\sqrt{n}) + n \qquad \qquad T(1) = \Theta(1)

Ở bài toán này, chúng ta tìm giá trị tiệm cận vì gía trị ban đầu của bài toán là hàm tiệm cận \Theta.

Dự đoán 1 :     T(n) = O(n \log n). Chúng ta dự đoán như vậy vì ở mỗi mức của cây đệ quy (sẽ giới thiệu ở dưới) bài toán có kích thước n. Thử chứng minh     T(n) \leq a n\log n.

 T(n) = \sqrt{n}T(\sqrt{n}) + n \leq \sqrt{n}\cdot a\sqrt{n}\log n +n \leq a n\log n

Ở bất đẳng thức cuối, ta giả sử  n \geq 2^{2/a} . Ok dự đoán của chúng ta là đúng. Bây giờ chúng ta thử chứng minh cận dưới    T(n) \geq bn\log n với một hằng số b nào đó (bài tập cho bạn đọc), ta sẽ thấy là không thể. Như vậy T(n) có thể nhỏ hơn nhiều n\log n

Dự đoán 2:     T(n) = O(n)   . Thử chứng minh    T(n) \leq a n.

T(n) = \sqrt{n}T(\sqrt{n}) + n \leq \sqrt{n}\cdot a\sqrt{n}  +n  = (a+1) n \nleq a n

Như vậy dự đoán chúng ta là sai.

Dự đoán 3:    T(n) = O(n\sqrt{n})   . Chứng minh tương tự ta thấy dự đoán này đúng. uy nhiên, nếu cố gắng chứng minh cận dưới T(n) = \Omega (n\sqrt{n}) chúng ta sẽ gặp vấn đề (bài tập cho bạn đọc)

Dự đoán 4:     T(n) = O(n\log\log n)   . Chứng minh cận trên  T(n) \leq a n\log\log n :

\begin{array} {lcl} T(n) & = & \sqrt{n}T(\sqrt{n}) + n \\
& \leq & \sqrt{n}\cdot a\sqrt{n} \log\log \sqrt{n} +n \\
& = & a n\log\log n -a n + n \\
& \leq & a n \log\log n\end{array}

Chứng minh cận dưới T(n) \geq b n\log\log n :

\begin{array} {lcl} T(n) & = & \sqrt{n}T(\sqrt{n}) + n \\
& \geq & \sqrt{n}\cdot b\sqrt{n} \log\log \sqrt{n} +n \\
& = & b n\log\log n -b n + n \\
& \geq & b n \log\log n \qquad \mbox{if } b\leq 1\end{array}

Như vậy ta có  T(n) = \Theta(n\log\log n)

Master theorem

Master theorem cung cấp cho ta cách giải hệ thức truy hồi trong Problem 1. Định lý dài và khó nhớ, tuy nhiên theo mình, các bạn đọc cách chứng minh để hiểu và vận dụng các chứng minh trong các bài toán đơn giản hơn sẽ dễ hơn là nhớ cả định lí.

Master Theorem: Cho hệ thức truy hồi:

 T(n) = aT(\frac{n}{b}) + f(n)

  1. Nếu  af(n/b) = \kappa f(n) với  \kappa < 1, ta có T(n) = \Theta(f(n))
  2. Nếu  af(n/b) = K f(n) với  K  data-recalc-dims= 1" />, ta có  T(n) = \Theta(n^{log_b a})
  3. Nếu  af(n/b) = f(n), ta có  T(n) = \Theta(f(n)\log_b n)

 
Chứng minh
 
Chúng ta sử dụng phương pháp cây đệ quy (recursion tree). Cây đệ quy có nút gốc có giá trị  f(n) 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, gía trị của hàm của các nút là  f(n/b^i). Minh họa ở hình sau:
Hình 1
 
Nhìn vào cây đệ quy ta sẽ thấy:

 
Ở đây  L là độ sâu của cây đệ quy. Dễ thấy,  L = \log_b n (tại sao) . Xét trường hợp:

  •  af(n/b)= f(n), ta có  a^if(n/b^i) = f(n). Do đó  T(n) = \Theta(f(n)\log_b n)
  •  af(n/b)= \kappa f(n), bằng quy nạp, ta có  a^if(n/b^i) = \kappa^i f(n). Do đó  T(n) = f(n) \sum_{i=1}^{L} \kappa^i = \Theta(f(n))\kappa < 1 ( geometric series)
  •  af(n/b)= K f(n) , chứng minh tương tự

 

Example 1 (Mergesort): T(n) = 2T(n/2) + n

Theo master theorem, af(n/b) = 2(n/2) = n = f(n), ta có T(n) = O(f(n)\log n) = n\log n.
 
Hoặc theo công thức tổng quát, T(n) = \sum_{i=1}^L 2^i n/2^i = \sum_{i=1}^L n = \Theta(n\log n)

.

Example 2 (Karatsuba's algorithm): T(n) = 3T(n/2) + n

Theo master theorem, af(n/b) = 3(n/2) = 1.5 n = Kf(n), ta có T(n) = O(n^{\log_b a}) = n^{\log_2 3}.
 
Hoặc theo công thức tổng quát, T(n) = \sum_{i=1}^L 3^i n/2^i = n\sum_{i=1}^{\log_2 n} (3/2)^i = n (3/2)^{\log_2n} = n^{\log_2 3}

.

Example 3 : T(n) = \sqrt{n}T(\sqrt{n}) + n

Master theorem không thể áp dụng trong trường hợp này.
 
Trường hợp này, nhìn vào cây nhị phân, ta thấy tổng gía trị mỗi mức là n, T(n) = \sum_{i=1}^L n với chiều cao cây L thỏa mãn n^{2^{-L}} = \Theta(1). Giải ra ta được L = \Theta(\log\log n). Như vậy T(n) = \Theta (n \log\log n)

.

Phương pháp "bom tấn"
 
Trong phần này chúng ta sẽ giải công thức đệ quy trong Problem 2 . Phương pháp ở phần này được đề xuất bởi Mohamad Akra và Louay Bazzi năm 1998. Với điều kiện k,a_i,b_i là các hằng số, lời giải của Problem 2 có dạng như sau:

T(n) = \Theta (n^\rho(1 + \int_1^n \frac{f(u)}{u^\rho +1}du))

Trong đó \rho thỏa mãn phương trình:

\sum_{i=1}^k a_i/b_i^\rho = 1

 
Chứng minh của định lí này có thể tham khảo ở [1]

Example 1 (Randomized Quicksort): T(n) = T(3n/4) + T(n/4) + n

Tìm \rho thỏa mã: (3/4)^\rho + (1/4)^\rho = 1 \Rightarrow \rho = 1. Áp dụng công thức tổng quát ta có:

T(n) = \Theta(n(1 + \int_{1}^n \frac{1}{u}du)) = O(n\log n)

 

Example 2 (Deterministic Selection): T(n) = T(n/5) + T(7n/10) + n

Tìm \rho thỏa mãn: (1/5)^\rho + (7/10)^\rho = 1 \Rightarrow 0 < \rho < 1. Áp dụng công thức tổng quát ta có:

T(n) = \Theta(n(1 + \int_{1}^n \frac{u}{u^{\rho + 1}}du)) = \Theta(n(1 + \Theta(n^{1 -\rho}) ) = \Theta(n)

Tham khảo
Bài viết chủ yếu dựa trên notes của Jef Erickson. Note này khá tốt để tham khảo. Các bạn sẽ học được rất nhiều từ bản gốc hơn là bài viết này.
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf>

Tài liệu tham khảo liên quan:
[1] Tom Leighton: Notes on Better Master Theorems for Divide-and-Conquer Recurrences , Manuscript. Massachusetts Institute of Technology, 1996, 9 pages

Bài tập luyện tập

Bài tập 1: Tìm giá trị tiệm cận của các hàm sau:

(a) A(n) = A(n-1) + 1 \qquad A(0)=0
(b) B(n) = B(n-1) + \frac{1}{n} \qquad B(0) = 0
(c) C(n) = C(n-2) + \frac{3}{n}  \qquad C(0) = C(1) = 0
(d) D(n) = (D(n-1))^2  \qquad D(0) = 2
(e) E(n) = E(n-1)E(n-2)  \qquad E(0) = 2, E(1)=1 (gợi ý: Viết lời giải dưới dạng dãy số Fibonacci)
(f) F(n) = \max_{1 \leq k \leq n}\{F(k-1) + F(n-k)\}

Bài tập 2: Sử dụng cây đệ quy hoặc phương pháp bom tấn để tìm giá trị tiệm cận của các hàm sau:

(a) A(n) = 2A(n/4) + \sqrt(n)
(b) B(n) = 2B(n/4) + n
(c) C(n) = 2C(n/4) + n^2
(d) D(n) = \sqrt{2n}D(\sqrt{2n}) + \sqrt(n)
(e) E(n) = 2E(n/3) + 2E(2n/3) + n
(f) F(n) = F(n/2) + F(n/3) + F(n/6) n

 
Bài tập 1 mình lấy từ Jeff Erickson Notes và bài tập 2 lấy từ Introduction to Algorithm, 2nd.

Tags: , ,

  1. hoahuongduong’s avatar

    Cái chỗ Công thức tổng quát trong ô vuông phải là f(n/b^i) chứ không phải T(n/b^i) anh à. Góp ý nhỏ thôi ^^

    Reply

    1. Hùng Lê’s avatar

      Ừ nhỉ. Mình gõ sai. Cám ơn bạn đã góp ý. (Góp ý này không hề nhỏ như bạn nghĩ :D).

      Hùng

      Reply

Reply

Your email address will not be published. Required fields are marked *