Giải Hệ Thức Truy Hồi

     
bài 2: Giải hệ thức truy tìm hồi

Trong bài bác này, chúng ta tìm hiểu một số cách giải cách làm truy hồi mà chúng ta hay chạm mặt trong so sánh thuật toán. Không hề ít hệ thức truy vấn hồi lộ diện trong phân tích thuật toán hoàn toàn có thể quy được về 1 trong hai câu hỏi tổng quát mắng sau:

Bài toán 1: Giải hệ thức tầm nã 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: Giải hệ thức truy hồi

Bài toán 2: Giải hệ thức tróc nã hồi: eginaligned T(n) = sum_i=1^k a_iT(fracnb_i) + f(n)qquad (2)endaligned trong những số ấy $a_i,b_i, i = 1,ldots, k$ là các hằng số dương.

Trong bài này, chúng ta sẽ tò mò 3 phương pháp 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. Cách thức đoán

Đây chắc hẳn rằng là phương pháp mà chúng ta thường hay nghĩ tới khi phát hiện một hệ thức tróc nã hồi.

Nguyên lý: dự đoán kết qủa và chứng tỏ bằng cách thức quy nạp.

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

Ví dụ 1 tra cứu 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 quý giá đầu tiên, ta thấy:eginaligned T(2) = 3, T(3) = 7, T(4) = 15, ldots endalignedKhông cạnh tranh để nhận biết 3 giá trị đầu nhất trí quy luật: $T(2) = 2^2-1$, $T(3) = 2^3-1$, $T(4) = 2^4-1$. Bởi vì đó, ta hoàn toàn có thể dự đoán $ T(n) = 2^n -1$.

Chứng minh: Theo giả thiết quy nạp, ta gồm $T(n-1) = 2^n-1-1$. Bởi đó:eginaligned T(n) = 2T(n-1) + 1 = 2(2^n-1-1) + 1 = 2^n -1endalignedĐây là dpcm.

Bây giờ bọn họ thử vận dụng cho vấn đề khó hơn

Ví dụ 2: tìm công thức tổng thể 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 chân thành và ý nghĩa $T(1)$ là một hằng số $c$ nào đó (ví dụ 2, 3 tuyệt 5). Với từng 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 hãy lựa chọn hằng số nào nhằm giải hệ thức trong ví dụ như 2? thực chất ta chỉ để ý đến giá trị tiệm cận của $T(n)$ theo vươn lên là $n$ chứ không phải một biểu thức đúng đắn của $n$. Coi lại bài tiệm cận tại đây.

Dự đoán 1 : $ T(n) = O(n log n)$.

Ghi chú 1: bạn cũng có thể hỏi vì sao lại đoán $O(nlog n)$; thực chất ở trên đây ta cứ chọn bừa một biểu thức nhưng mà ta cảm giác hợp lý; nuốm vào đó, chúng ta cũng có thể chọn dự kiến $O(n^2)$.

Giờ ta thử chứng tỏ $T(n) leq a nlog n$. Điểm cốt yếu ở đó là khái niệm $O(.)$ cho phép ta tùy ý lựa chọn chọn hằng số $a$ với giá trị bé bỏng nhất của $n$ để dự đoán của họ 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 mang sử $ n geq 2^2/a $. Như vậy, dự kiến của bọn họ là đúng.

Ghi chú 2: có vẻ như ta đang “tuỳ tiện” giả sử $n geq 2^2/a$. Thực chất đây ko phải là 1 trong những giả sử tuỳ tiện. Bạn cũng có thể giả sử $n$ “lớn tuỳ ý”. Để hiểu tại sao ta lại được phép đưa sử như vậy, bạn phải xem lại quan niệm của big-O.

Bây giờ chúng ta thử minh chứng cận bên dưới $T(n) geq bnlog n$ bởi quy nạp với $b$ là một hằng số làm sao đó.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 và chỉ còn khi $n geq b/2 nlog n$. Điều này là ko thể xẩy ra vì với mọi quý giá của hằng số $b$, luôn luôn tồn tại $n$ đủ lớn nhằm $ fracb2 nlog n

Ghi chú 3: thực ra ta đã minh chứng $T(n) = O(n log n)$, và bởi $nlog n = O(nsqrtn)$ yêu cầu hiển nhiên $T(n) = O(nsqrtn)$. Coi lại đặc thù 1 của bài tiệm cận.

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

eginarray lcl T(n) và = và sqrtnT(sqrtn) + n \& leq & sqrtncdot asqrtn loglog sqrtn +n \& = & a nloglog n -a n + n \& leq & a n loglog nendarray

khi $a geq 2$. Giờ đồng hồ ta chỉ việc chứng minh cận bên dưới $T(n) geq b nloglog n$:

eginarray lcl T(n) và = và sqrtnT(sqrtn) + n \& geq và sqrtncdot bsqrtn loglog sqrtn +n \& = & b nloglog n -b n + n \& geq & 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à một trong những công cụ giúp ta giải những hệ thức truy tìm hồi gồm dạng trong câu hỏi 1. Định lý nhiều năm và cực nhọc nhớ với theo mình độc giả cũng không yêu cầu nhớ làm cho gì. Chỉ cần nhớ dạng vấn đề mà định lý này có thể áp dụng nhằm giải. Nếu rất có thể thì chỉ cần nhớ phương pháp chứng minh định lý.


Định lý thợ
: đến hệ thức truy hỏi hồi:eginaligned T(n) = aT(fracnb) + f(n)endalignedNếu $ af(n/b) = kappa f(n)$ với $ kappa giả dụ $ af(n/b) = K f(n)$ với $ K > 1$, ta tất cả $ T(n) = Theta(n^log_b a)$.Nếu $ af(n/b) = f(n)$, ta tất cả $ T(n) = Theta(f(n)log_b n)$.

Chứng minh: bọn họ sử dụng phương thức cây đệ quy. Cây đệ quy gồm 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 gốc sẽ là gốc của một cây mang đến hàm đệ quy $ T(n/b)$. Như vậy, ở độ sâu trang bị $ i$, quý giá của hàm của những nút là $ f(n/b^i)$. Coi minh hoạ trong hình 1.

Xem thêm: Những Lời Chúc Hay Ngày 19 8 Ý Nghĩa Nhất, Lời Chúc Ngày Công An Nhân Dân Việt Nam 19/8

*

Hình 1: Minh hoạ cây đệ quy giải hệ thức tầm nã hồi vào định lý thợ. Hình được giảm từ tài liệu tìm hiểu thêm <1>.

Sử dụng cây đệ quy ta suy ra:eginalignedT(n) = sum_i=1^L a^i f(fracnb^i)qquad (1)endalignedỞ đâ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 1 mức của cây đệ quy, quý hiếm của $n$ giảm đi $b$ lần. Xét trường hợp:

TH1: $ af(n/b)= f(n)$, ta có $ a^if(n/b^i) = f(n)$. Điều này có nghĩa là tổng cực hiếm tại từng mức của cây là $f(n)$. Vày 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 cách thức quy nạp giống như 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à do $K leq a$ bởi $af(n/b)leq a f(n)$ bởi vì $f(.)$ là một trong những hàm đơn điệu tăng theo $n$ lúc $n$ đầy đủ lớn.

Ta xét một vài lấy một ví dụ ứng dụng.

Ví dụ 3: tìm tiệm cận của $T(n)$ hiểu được $T(n) = 2T(n/2) + n$.

Lời giải: do $af(n/b) = 2(n/2) = n = f(n)$, theo định lý thợ, ta gồm $T(n) = O(f(n)log n) = O(nlog n)$.

Trong ví dụ 3, ta cũng có thể dùng cách làm trong phương trình (1) để tính. Cầm thể, $T(n) = sum_i=1^L 2^i n/2^i = sum_i=1^L n = Theta(nlog n)$.

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

Lời giải: vày $af(n/b) = 3(n/2) = 1.5 n = Kf(n)$ cùng với $K = 1.5$, theo định lý thợ, ta bao gồm $T(n) = O(n^log_b a) =O( n^log_2 3)$. 

Nếu sử 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: tìm tiệm cận của $T(n)$ biết rằng $T(n) = sqrtnT(sqrtn) + n$.

Lời giải: vì chưng dạng của phương trình đệ quy này sẽ không giống cùng với dạng trong định lý thợ, ta ko thể vận dụng công thức bao quát 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. Nhìn vào cây nhị phân, ta thấy tổng vốn mỗi nút là $n$. Vị đó, $T(n) = sum_i=1^L n$ với độ cao cây $L$. Không cực nhọc để thấy rằng $L$ thỏa mãn phương trình $n^2^-L = Theta(1)$. Giải ra ta được $L = Theta(loglog n)$. Do vậy $T(n) = Theta (n loglog n)$.

Ghi chú 4: Định lý thợ tương đối dài loại và cực nhọc nhớ. Thực tế ta không tốt nhất thiết đề xuất nhớ chi tiết định lý này. Hai điều cần nhớ tự định lý này là: (a) có một công thức tổng thể để ta hoàn toàn có thể tra cứu giúp và so sánh khi yêu cầu dùng và (b) phương pháp cây đệ quy nhằm giải hệ thức truy hồi. Về phiên bản chất, phương thức cây nhị phân mới là vấn đề cần ghi nhớ nghỉ ngơi đây.

Phương pháp “bom tấn”

Trong phần này bọn họ sẽ tò mò một vẻ ngoài rất to gan lớn mật để giải bí quyết đệ quy bao gồm dạng trong việc 2. Phương pháp được lời khuyên bởi Mohamad Akra và Louay Bazzi năm 1998. Với đk $k,a_i,b_i$ là những hằng số, giải thuật của vấn đề 2 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 chứng tỏ của định lí này vào <2>.

Ví dụ 6: tra cứu tiệm cận của $T(n)$ hiểu được eginalignedT(n) = T(3n/4) + T(n/4) + n.endaligned

Lời giải: Áp dụng phương trình (2), ta tìm $ ho$ thỏa mãn nhu cầu phương trình (3): $(3/4)^ ho + (1/4)^ ho = 1$. Dễ thấy giải mã ở đấy 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 kiếm tiệm cận của $T(n)$ hiểu được 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 cực nhọc để thấy $ ho$ đã là một số trong những nằm trong khoảng $(0,1)$. (Ta có thể sử áp dụng wolframalpha để 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, chú ý 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ập

Bài tập 1: Tìm cực hiếm tiệm cận của các 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 những 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 kinh điể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: Nồi Cơm Điện Cuckoo Cr-1021, Nồi Cơm Điện Cơ 1,8L Cuckoo Cr

Bài tập 1 được lấy từ Jeff Erickson Notes và bài tập 3 rước từ Introduction khổng lồ Algorithm, 2nd.