Trong bài bác này, họ tìm hiểu một số trong những cách giải phương pháp truy hồi mà họ hay gặp trong phân tích thuật toán. Rất nhiều hệ thức truy hỏi hồi lộ diện trong so sánh thuật toán hoàn toàn có thể quy được về 1 trong các hai vấn đề tổng quát lác sau:
Bài toán 1: Giải hệ thức truy hồi: eginaligned T(n) = aT(fracnb) + f(n) qquad (1)endaligned trong những số đó $a,b$ là các hằng số dương.
Bạn đang xem: Hệ thức truy hồi
và
Bài toán 2: Giải hệ thức truy vấn hồi: eginaligned T(n) = sum_i=1^k a_iT(fracnb_i) + f(n)qquad (2)endaligned trong các số ấy $a_i,b_i, i = 1,ldots, k$ là những hằng số dương.
Trong bài này, chúng ta sẽ tìm hiểu 3 cách thức giải. Mỗi cách thức có ưu cùng nhược điểm riêng rẽ của nó. Ta ban đầu với phương thức đơn giản nhất.
1. Phương thức đoánĐây chắc rằng là phương thức mà chúng ta thường giỏi nghĩ tới khi bắt gặp một hệ thức truy tìm hồi.
Nguyên lý: dự đoán kết qủa và minh chứng bằng phương thức quy nạp.
Theo nguyên lý, ta chỉ dễ dàng và đơn giản giải hệ thức truy nã hồi bằng phương pháp đoán nghiệm, thử minh chứng và đoán lại. Để minh hoạ, xét một vài lấy ví dụ sau.
Ví dụ 1 tìm công thức bao quát của $T(n)$ biết rằng:eginaligned T(n) = 2T(n-1) + 1 qquad qquad T(1) = 1 endaligned
Thử một vài cực hiếm đầu tiên, ta thấy:eginaligned T(2) = 3, T(3) = 7, T(4) = 15, ldots endalignedKhông khó khăn để nhận ra 3 quý giá đầu chấp thuận quy luật: $T(2) = 2^2-1$, $T(3) = 2^3-1$, $T(4) = 2^4-1$. Do đó, ta hoàn toàn có thể dự đoán $ T(n) = 2^n -1$.
Chứng minh: Theo mang thiết quy nạp, ta có $T(n-1) = 2^n-1-1$. Bởi vì đó:eginaligned T(n) = 2T(n-1) + 1 = 2(2^n-1-1) + 1 = 2^n -1endalignedĐây là dpcm.
Bây giờ họ thử áp dụng cho việc khó hơn
Ví dụ 2: search công thức bao quát của $T(n)$ biết rằng: eginaligned T(n) = sqrtnT(sqrtn) + n qquad qquad T(1) = Theta(1) endaligned
Trong hệ thức trên, $T(1) = Theta(1)$ mang ý nghĩa sâu sắc $T(1)$ là một trong những hằng số $c$ nào kia (ví dụ 2, 3 hay 5). Với mỗi hằng số, lúc giải hệ thức, ta tìm được một $T(n)$ không giống nhau. Do đó ta nên chọn hằng số nào để giải hệ thức trong ví dụ 2? thực chất ta chỉ xem xét giá trị tiệm cận của $T(n)$ theo biến đổi $n$ chứ chưa phải một biểu thức chính xác của $n$. Xem lại bài xích tiệm cận tại đây.
Dự đoán 1 : $ T(n) = O(n log n)$.
Ghi chú 1: chúng ta cũng có thể hỏi tại sao lại đoán $O(nlog n)$; thực chất ở đây ta cứ chọn bừa một biểu thức nhưng ta cảm giác hợp lý; cụ vào đó, chúng ta cũng có thể chọn dự kiến $O(n^2)$.
Giờ ta thử chứng minh $T(n) leq a nlog n$. Điểm cốt yếu ở đó là khái niệm $O(.)$ được cho phép ta tùy ý chọn chọn hằng số $a$ và giá trị bé nhỏ nhất của $n$ để dự đoán của chúng ta là đúng.eginaligned T(n) = sqrtnT(sqrtn) + n leq sqrtncdot asqrtnlog sqrtn +n leq a nlog n endalignedỞ bất đẳng thức cuối, ta trả sử $ n geq 2^2/a $. Như vậy, dự đoán của bọn họ là đúng.
Ghi chú 2: có vẻ như như ta vẫn “tuỳ tiện” trả sử $n geq 2^2/a$. Thực ra đây ko phải là 1 trong giả sử tuỳ tiện. Chúng ta có thể giả sử $n$ “lớn tuỳ ý”. Để hiểu nguyên nhân ta lại được phép giả sử như vậy, bạn cần xem lại tư tưởng của big-O.
Bây giờ bọn họ thử chứng minh cận dưới $T(n) geq bnlog n$ bằng quy nạp với $b$ là 1 trong hằng số như thế nào đó.eginaligned T(n) = sqrtnT(sqrtn) + n geq sqrtncdot bsqrtnlog sqrtn +n = fracb2 nlog n + n endaligned
Giá trị này to hơn $b n log n$ khi còn chỉ khi $n geq b/2 nlog n$. Điều này là không thể xẩy ra vì với mọi quý giá của hằng số $b$, luôn tồn tại $n$ đủ lớn để $ fracb2 nlog n
Ghi chú 3: thực ra ta đã chứng tỏ $T(n) = O(n log n)$, và vày $nlog n = O(nsqrtn)$ phải hiển nhiên $T(n) = O(nsqrtn)$. Coi lại đặc điểm 1 của bài tiệm cận.
Dự đoán 4: $T(n) = O(nloglog n)$. Minh chứng cận trên $ T(n) leq a nloglog n $:
eginarray lcl T(n) & = & sqrtnT(sqrtn) + n \& leq & sqrtncdot asqrtn loglog sqrtn +n \& = và a nloglog n -a n + n \& leq & a n loglog nendarray
khi $a geq 2$. Giờ đồng hồ ta chỉ cần chứng minh cận dưới $T(n) geq b nloglog n$:
eginarray lcl T(n) & = và sqrtnT(sqrtn) + n \& geq & sqrtncdot bsqrtn loglog sqrtn +n \& = & b nloglog n -b n + n \& geq và b n loglog n qquad mboxnếu b leq 1endarray
Do đó, ta rất có thể kết luận $T(n) = Theta(nloglog n)$.
Định lý thợĐịnh lý thợ (master theorem) là 1 trong những công vậy giúp ta giải những hệ thức tróc nã hồi bao gồm dạng trong câu hỏi 1. Định lý nhiều năm và cực nhọc nhớ và theo mình bạn đọc cũng không cần nhớ làm cho gì. Chỉ cần nhớ dạng việc mà định lý này hoàn toàn có thể áp dụng để giải. Nếu có thể thì chỉ cần nhớ cách thức chứng minh định lý.
Định lý thợ: mang lại hệ thức truy tìm hồi:eginaligned T(n) = aT(fracnb) + f(n)endalignedNếu $ af(n/b) = kappa f(n)$ cùng với $ kappa nếu như $ af(n/b) = K f(n)$ với $ K > 1$, ta gồm $ T(n) = Theta(n^log_b a)$.Nếu $ af(n/b) = f(n)$, ta bao gồm $ T(n) = Theta(f(n)log_b n)$.
Chứng minh: bọn họ sử dụng cách thức cây đệ quy. Cây đệ quy tất cả nút gốc có mức giá trị $ f(n)$ cùng $ a$ nút con. Mỗi nút nhỏ của nút nơi bắt đầu sẽ là nơi bắt đầu của một cây đến hàm đệ quy $ T(n/b)$. Như vậy, sống độ sâu lắp thêm $ i$, quý giá của hàm của những nút là $ f(n/b^i)$. Xem minh hoạ vào hình 1.
Hình 1: Minh hoạ cây đệ quy giải hệ thức truy hỏi hồi vào định lý thợ. Hình được giảm từ tài liệu tham khảo <1>.
Sử dụng cây đệ quy ta suy ra:eginalignedT(n) = sum_i=1^L a^i f(fracnb^i)qquad (1)endalignedỞ trên đây $ L$ là độ sâu của cây đệ quy. Dễ thấy, $ L = log_b n$ do những lần đi xuống sâu thêm một mức của cây đệ quy, giá trị của $n$ sụt giảm $b$ lần. Xét ngôi trường hợp:
TH1: $ af(n/b)= f(n)$, ta tất cả $ a^if(n/b^i) = f(n)$. Điều này tức là tổng cực hiếm tại từng mức của cây là $f(n)$. Vị cây có $L$ mức, ta suy ra:eginalignedT(n) = Theta(f(n) L) = Theta(f(n)log_b n).endaligned TH3: $af(n/b)= K f(n)$, sử dụng phương pháp quy nạp tương tự TH2, ta suy ra $ a^if(n/b^i) = K^i f(n)$. Như vậy,eginalignedT(n) = f(n) sum_i=1^L K^i = Theta(f(n)K^L+1) = Theta(n^log_b(K)) = Theta(n^log_b(a)).endalignedPhương trình cuối là vì $K leq a$ vày $af(n/b)leq a f(n)$ vị $f(.)$ là 1 trong những hàm đơn điệu tăng theo $n$ khi $n$ đủ lớn.Ta xét một vài lấy một ví dụ ứng dụng.
Ví dụ 3: tìm kiếm tiệm cận của $T(n)$ biết rằng $T(n) = 2T(n/2) + n$.
Lời giải: vì chưng $af(n/b) = 2(n/2) = n = f(n)$, theo định lý thợ, ta có $T(n) = O(f(n)log n) = O(nlog n)$.
Trong lấy ví dụ như 3, ta cũng rất có thể dùng công thức trong phương trình (1) để tính. Rứa thể, $T(n) = sum_i=1^L 2^i n/2^i = sum_i=1^L n = Theta(nlog n)$.
Ví dụ 4: search tiệm cận của $T(n)$ hiểu được $T(n) = 3T(n/2) + n$.
Lời giải: vì $af(n/b) = 3(n/2) = 1.5 n = Kf(n)$ với $K = 1.5$, theo định lý thợ, ta gồm $T(n) = O(n^log_b a) =O( n^log_2 3)$.
Nếu áp dụng công thức (1) trong ví dụ 4, ta có:eginalignedT(n) = sum_i=1^L 3^i n/2^i = nsum_i=1^log_2 n (3/2)^i = n (3/2)^log_2n = n^log_2 3. endaligned
Ví dụ 5: tra cứu tiệm cận của $T(n)$ hiểu được $T(n) = sqrtnT(sqrtn) + n$.
Lời giải: bởi vì dạng của phương trình đệ quy này không giống với dạng trong định lý thợ, ta ko thể vận dụng công thức tổng thể của định lý thợ. Mặc dù nhiên, ta rất có thể áp dụng trực tiếp cách thức cây đệ quy. Quan sát vào cây nhị phân, ta thấy tổng mức mỗi mức là $n$. Vày đó, $T(n) = sum_i=1^L n$ với chiều cao cây $L$. Không nặng nề để thấy rằng $L$ thỏa mãn nhu cầu phương trình $n^2^-L = Theta(1)$. Giải ra ta được $L = Theta(loglog n)$. Vậy nên $T(n) = Theta (n loglog n)$.
Ghi chú 4: Định lý thợ khá dài cái và khó khăn nhớ. Thực ra ta không độc nhất thiết cần nhớ chi tiết định lý này. Hai vấn đề cần nhớ trường đoản cú định lý này là: (a) tất cả một công thức tổng thể để ta có thể tra cứu vãn và so sánh khi yêu cầu dùng cùng (b) phương thức cây đệ quy để giải hệ thức tróc nã hồi. Về phiên bản chất, phương pháp cây nhị phân mới là điều cần ghi nhớ sinh sống đây.
Phương pháp “bom tấn”Trong phần này chúng ta sẽ khám phá một chính sách rất bạo dạn để giải công thức đệ quy tất cả dạng trong câu hỏi 2. Phương thức được khuyến nghị bởi Mohamad Akra với Louay Bazzi năm 1998. Với đk $k,a_i,b_i$ là các hằng số, giải thuật của bài toán 2 bao gồm dạng như sau:
eginalignedT(n) = Theta (n^ ho(1 + int_1^n fracf(u)u^ ho +1du)) qquad (2)endaligned
Bạn đọc rất có thể tham khảo minh chứng của định lí này trong <2>.
Ví dụ 6: search tiệm cận của $T(n)$ biết rằng eginalignedT(n) = T(3n/4) + T(n/4) + n.endaligned
Lời giải: Áp dụng phương trình (2), ta search $ ho$ thỏa mãn phương trình (3): $(3/4)^ ho + (1/4)^ ho = 1$. Dễ dàng thấy lời giải ở đó là $ ho = 1$. Bởi vì đó, ta có:eginaligned T(n) = Theta(n(1 + int_1^n fracuu^2du)) = O(nlog n)endaligned
Ví dụ 7: tìm tiệm cận của $T(n)$ biết rằng eginalignedT(n) = T(n/5) + T(7n/10) + n.endaligned
Lời giải: Ta tìm kiếm $ ho$ thỏa mãn: $(1/5)^ ho + (7/10)^ ho = 1$. Không khó khăn để thấy $ ho$ đã là một số nằm trong vòng $(0,1)$. (Ta hoàn toàn có thể sử sử dụng wolframalpha nhằm tìm $ ho$). Áp dụng công thức tổng quát ta có:
$ T(n) = Theta(n^ ho(1 + int_1^n fracuu^ ho + 1du)) = Theta(n^ ho(1 + Theta(n^1 - ho) ) = Theta(n)$
Tham khảo<1> J. Erickson, lưu ý on Recurrence Relation, UIUC, Fall 2013.
<2> T. Leighton: Notes on Better Master Theorems for Divide-and-Conquer Recurrences , Manuscript. MIT, 1996.
Bài tậpBài tập 1: Tìm giá trị tiệm cận của những hàm sau:
$A(n) = A(n-1) + 1 qquad A(0)=0$. $B(n) = B(n-1) + frac1n qquad B(0) = 0$. $C(n) = C(n-2) + frac3n qquad C(0) = C(1) = 0$. $D(n) = (D(n-1))^2 qquad D(0) = 2$. $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 hàng số Fibonacci.).Bài tập 2: sử dụng định lý thợ, tìm kiếm tiệm cận của các hàm sau:
$A(n) = A(n/2) + O(1)$. $B(n) = 4B(n/2) + O(n)$. $C(n) = 3C(n/2) + O(n)$. $D(n) = 7 D(n/2) + O(n^2)$.Bài tập 3: sử dụng cây đệ quy hoặc phương pháp bom tấn để tìm quý hiếm tiệm cận của các hàm sau:
$A(n) = 2A(n/4) + sqrtn$. $B(n) = 2B(n/4) + n$. $C(n) = 2C(n/4) + n^2$. $D(n) = sqrt2nD(sqrt2n) + sqrtn$. $E(n) = 2E(n/3) + 2E(2n/3) + n$. $F(n) = 2 F(n/2) + O(nlog n)$.Xem thêm: Nhân Ngày 20-11 Kể Cho Các Bạn Nghe Về Một Kỉ Niệm Đáng Nhớ Giữa Mình Và Thầy Cô Giáo Cũ
Bài tập 1 được mang từ Jeff Erickson Notes và bài tập 3 đem từ Introduction lớn Algorithm, 2nd.