Công thức truy hồi là những công thức quan trọng giúp các em lớp 11, lớp 12 cần ghi nhớ để vận dụng tính toán nhanh nhất các bài toán truy hồi và cho ra kết quả chính xác.
Trong kì thi THPT Quốc gia môn Toán thì số lượng công thức cần ghi nhớ là không hề nhỏ. Đối với các bài thi trắc nghiệm, điều cần thiết là các em học sinh cần nắm kiến thức rộng và có phương pháp giải nhanh hiệu quả để có thể ghi điểm nhiều nhất. Bên cạnh công thức truy hồi các bạn xem thêm bộ đề ôn thi THPT Quốc gia môn Toán, phân dạng câu hỏi và bài tập trong đề thi THPT Quốc gia môn Toán.
1. Nội dung chính tài liệu công thức truy hồi
Dạng 1: Tìm số hạng tổng quát của dãy số [dạng đa thức] khi biết các số hạng đầu tiên
Dạng 2: Dạng cơ sở: Cho dãy [un] biết u1 = a và un+1 = q.un + d ∀ n ≥ 1 với q, d là các hằng số thực
Gồm 4 trường hợp, dạng này được gọi là dạng cơ sở vì:
+ Với 3 trường hợp 1, 2, và 3 dãy số trở thành các dãy đặc biệt đó là: dãy số hằng, cấp số cộng và cấp số nhân. Các dãy số này ta đều đã tìm được công thức của số hạng tổng quát.
+ Trên cơ sở của 3 dãy này, để giải trường hợp 4: bằng phương pháp đặt một dãy số mới [vn] liên hệ với dãy số [un] bằng một biểu thức nào đó để có thể đưa được về dãy số [vn] mà [vn] dãy số hằng hoặc cấp cộng hoặc cấp số nhân.
+ Vấn đề đặt ra là: Mối liên hệ giữa [un] và [vn] bởi biểu thức nào mới có thể đưa dãy số [vn] thành dãy số hằng hoặc cấp số cộng hoặc cấp số nhân hoặc trường hợp 4.
2. Cách tìm công thức truy hồi
Dạng 1: Tìm số hạng tổng quát của dãy số [dạng đa thức] khi biết các số hạng đầu tiên
Ví du 1.1: Cho dãy số ] có dạng khai triển sau: 1 ;-1 ;-1 ; 1 ; 5 ; 11 ; 19 ; 29 ; 41 ; 55 ; ........
Hãy tìm công thức của số hạng tổng quát và tìm số tiếp theo?
Bài giải
Nhận xét: Với 10 số hạng đầu thế này, để tìm ra quy luật biểu diễn là rất khó. Với những cách cho này ta thường làm phương pháp sau:
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. Mục tiêu chính của bài viết là cung cấp một số công cụ chuẩn để bạn đọc có thể ước lượng được nhanh chóng giá trị tiệm cận của hàm truy hồi mà bạn đọc quan tâm. Bài viết này chủ yếu tóm lược lại note của Jeff Erickson [1]. Mình khuyến khích bạn đọc xem bản gốc.
Rất nhiều hệ thức truy hồi xuất hiện trong phân tích thuật toán có thể quy được về một trong hai bài toán tổng quát sau:
Problem 1: giải hệ thức truy hồi:
$ T[n] = aT[\frac{n}{b}] + f[n] \qquad [1]$
trong đó $a,b$ là các hằng số dương.
Problem 2: giải hệ thức truy hồi:
$ T[n] = \sum_{i=1}^k a_iT[\frac{n}{b_i}] + f[n]\qquad [2]$
trong đó $a_i,b_i, i = 1,\ldots, k$ là các hằng số dương.
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
Ví dụ 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
Ví dụ 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ì giá 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$. Điểm mấu chốt ở đây là khái niệm $O[.]$ cho phép ta tùy ý chọn chọn hằng số $a$ và giá trị bé nhất của $n$ để dự đoán của chúng ta là đúng.
$ T[n] = \sqrt{n}T[\sqrt{n}] + n \leq \sqrt{n}\cdot a\sqrt{n}\log \sqrt{n} +n \leq a n\log n $
Ở bất đẳng thức cuối, ta giả sử $ n \geq 2^{2/a} $. Như vậy, 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$ bằng quy nạp.
$ T[n] = \sqrt{n}T[\sqrt{n}] + n \geq \sqrt{n}\cdot b\sqrt{n}\log \sqrt{n} +n = \frac{b}{2} n\log n + n$
Giá trị này lớn hơn $b n \log n$ khi và chỉ khi $n \geq b/2 n\log n$. Điều này là không thể vì với mọi giá trị của hằng số $b$, luôn tồn tại $n$ đủ lớn để $ b/2 n\log n $ > $ n$. Như vậy, cận trên $O[n\log n]$ vẫn chưa chặt.
Dự đoán 2: $T[n] = O[n]$. Ta lặp lại ý tưởng ở trê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. Tuy 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}
khi $a \geq 2$. Giờ ta chỉ cần 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{nếu } b \leq 1\end{array}
Do đó, ta có thể kết luận $T[n] = \Theta[n\log\log n]$.
Đị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 . Đị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ý.
Master Theorem: Cho hệ thức truy hồi:
$ T[n] = aT[\frac{n}{b}] + f[n]$
- Nếu $ af[n/b] = \kappa f[n]$ với $ \kappa < 1$, ta có $T[n] = \Theta[f[n]]$.
- Nếu $ af[n/b] = K f[n]$ với $ K > 1$, ta có $ T[n] = \Theta[n^{\log_b a}]$.
- 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]$ 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$, gía trị của hàm của các nút là $ f[n/b^i]$. Minh họa ở hình sau:
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$. 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ó thể chứng minh được $ a^if[n/b^i] = \kappa^i f[n]$. Do đó $ T[n] = f[n] \sum_{i=1}^{L} \kappa^i = \Theta[f[n]]$ vì $\kappa < 1 $ [geometric series]
- $ af[n/b]= K f[n] $, chứng minh tương tự. Chi tiết coi như bài tập cho bạn đọc.
Ví dụ 1 [Mergesort]: $T[n] = 2T[n/2] + n$. Do $af[n/b] = 2[n/2] = n = f[n]$, theo định lý thợ, ta có $T[n] = O[f[n]\log n] = O[n\log n]$.
Ta cũng có thể dùng công thức tổng quát để tính. Cụ thể, $T[n] = \sum_{i=1}^L 2^i n/2^i = \sum_{i=1}^L n = \Theta[n\log n]$.
Ví dụ 2 [Karatsuba's algorithm]: $T[n] = 3T[n/2] + n$. Do $af[n/b] = 3[n/2] = 1.5 n = Kf[n]$ với $K = 1.5$, theo định lý thợ, ta có $T[n] = O[n^{\log_b a}] =O[ n^{\log_2 3}]$.
Hoặc sử dụng công thức tổng quát, ta có $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}$.
Ví dụ 3: $T[n] = \sqrt{n}T[\sqrt{n}] + n$. Do dạng của phương trình đệ quy này không giống với dạng trong định lý thợ, ta không thể áp dụng công thức tổng quát của định lý thợ. Tuy nhiên, ta có thể áp dụng phương pháp cây đệ quy. Nhìn vào cây nhị phân, ta thấy tổng giá 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ẽ tìm hiểu một công cụ khác công thức đệ quy có dạng trong . Phương phápđượ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 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$
Bạn đọc có thể tham khảo chứng minh của định lí này trong [2].
Ví dụ 4 [Randomized Quicksort]: $T[n] = T[3n/4] + T[n/4] + n$. Áp dụng công thức tổng quát, ta tìm $\rho$ thỏa mãn: $[3/4]\rho + [1/4]\rho = 1$. Dễ thấy $\rho = 1$. Do đó, ta có:
$ T[n] = \Theta[n[1 + \int_{1}^n \frac{1}{u}du]] = O[n\log n]$
Ví dụ 5 [Deterministic Selection] $T[n] = T[n/5] + T[7n/10] + n$. Ta tìm $\rho$ thỏa mãn: $[1/5]\rho + [7/10]\rho = 1$. Ta sẽ tìm được một giá trị [sử dụng wolframalpha] $\rho$ thỏa mãn $ 0 < \rho < 1$. Áp dụng công thức tổng quát ta có:
$ T[n] = \Theta[n^{\rho}[1 + \int_{1}n \frac{u}{u{\rho + 1}}du]] = \Theta[n^{\rho}[1 + \Theta[n^{1 -\rho}] ] = \Theta[n]$