Giải hệ thức truy hồi

     
bài 2: Giải hệ thức tróc nã hồi

Trong bài xích này, bọn họ tìm hiểu một số cách giải công thức truy hồi mà họ hay chạm mặt trong đối chiếu thuật toán. Không hề ít hệ thức truy hồi xuất hiện thêm trong đối chiếu thuật toán hoàn toàn có thể quy được về 1 trong hai bài toán tổng quát tháo sau:

Bài toán 1: Giải hệ thức truy tìm hồi: eginaligned T(n) = aT(fracnb) + f(n) qquad (1)endaligned trong những số đó $a,b$ là những 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 số đó $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 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 biệt của nó. Ta bước đầu với phương pháp đơ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 tốt nghĩ tới khi phát hiện một hệ thức tầm nã hồi.

Nguyên lý: dự kiến kết qủa và chứng minh bằng phương thức quy nạp.

Theo nguyên lý, ta chỉ đơn giản giải hệ thức tầm nã 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ụ như sau.

Ví dụ 1 tìm công thức tổng thể 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ực nhọc để phân biệt 3 giá trị đầu đồng tình quy luật: $T(2) = 2^2-1$, $T(3) = 2^3-1$, $T(4) = 2^4-1$. Vày đó, ta có thể dự đoán $ T(n) = 2^n -1$.

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

Bây giờ họ thử vận dụng cho việc khó hơn

Ví dụ 2: tra cứu 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 ý nghĩa $T(1)$ là 1 trong những hằng số $c$ nào kia (ví dụ 2, 3 xuất xắc 5). Với mỗi hằng số, khi giải hệ thức, ta tìm kiếm được một $T(n)$ khác nhau. Do đó ta nên chọn hằng số nào để giải hệ thức trong ví dụ 2? thực tế ta chỉ quan tâm đến giá trị tiệm cận của $T(n)$ theo vươn lên là $n$ chứ không hẳn một biểu thức đúng mực của $n$. Coi lại bài bác 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 nguyên nhân lại đoán $O(nlog n)$; thực ra ở đây ta cứ chọn bừa một biểu thức nhưng mà ta cảm giác hợp lý; rứa 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 chủ chốt ở đó là khái niệm $O(.)$ chất nhận được ta tùy ý lựa chọn chọn hằng số $a$ với giá trị nhỏ nhắn nhất của $n$ để tham gia đoán của bọn 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ự đoán của bọn họ là đúng.

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

Bây giờ chúng ta thử minh chứng cận dưới $T(n) geq bnlog n$ bởi quy hấp thụ với $b$ là 1 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 lớn 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 giá trị 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 minh $T(n) = O(n log n)$, và vì $nlog n = O(nsqrtn)$ cần 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)$. Chứng minh cận trên $ T(n) leq a nloglog n $:

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

khi $a geq 2$. Tiếng 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 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 hoàn toàn 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 rứa giúp ta giải những hệ thức truy hồi gồm dạng trong việc 1. Định lý nhiều năm và khó khăn nhớ và theo mình độc giả cũng không nên nhớ làm cho gì. Chỉ cần nhớ dạng câu hỏi mà định lý này hoàn toàn 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ợ
: cho hệ thức tầm nã hồi:eginaligned T(n) = aT(fracnb) + f(n)endalignedNếu $ af(n/b) = kappa f(n)$ cùng với $ kappa ví như $ af(n/b) = K f(n)$ cùng 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: chúng ta sử dụng cách thức cây đệ quy. Cây đệ quy tất cả nút gốc có giá trị $ f(n)$ cùng $ a$ nút con. Từng 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 mang đến hàm đệ quy $ T(n/b)$. Như vậy, sinh hoạt độ sâu trang bị $ i$, giá trị của hàm của những nút là $ f(n/b^i)$. Coi minh hoạ vào hình 1.

Xem thêm: Soạn Bài Câu Cá Mùa Thu Hay Nhất, Soạn Bài Câu Cá Mùa Thu Ngắn Gọn

*

Hình 1: Minh hoạ cây đệ quy giải hệ thức truy nã hồi trong định lý thợ. Hình được giảm từ tài liệu xem 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Ở trên đây $ L$ là độ sâu của cây đệ quy. Dễ dàng thấy, $ L = log_b n$ do các lần đi xuống sâu thêm 1 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ó $ a^if(n/b^i) = f(n)$. Điều này tức là tổng quý hiếm tại mỗi mức của cây là $f(n)$. Vì chưng 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 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ì chưng $af(n/b)leq a f(n)$ vì chưng $f(.)$ là một trong hàm 1-1 điệu tăng theo $n$ lúc $n$ đủ lớn.

Ta xét một vài ví dụ như ứng dụng.

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

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

Trong lấy một ví dụ 3, ta cũng có thể dùng công thức trong phương trình (1) nhằm tính. Thế 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ị $af(n/b) = 3(n/2) = 1.5 n = Kf(n)$ với $K = 1.5$, theo định lý thợ, ta tất cả $T(n) = O(n^log_b a) =O( n^log_2 3)$. 

Nếu thực hiện 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: vì dạng của phương trình đệ quy này sẽ 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 thể của định lý thợ. Tuy nhiên, ta 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 giá trị mỗi nút là $n$. Bởi vì đó, $T(n) = sum_i=1^L n$ với độ cao cây $L$. Không khó khăn để thấy rằng $L$ vừa lòng phương trình $n^2^-L = Theta(1)$. Giải ra ta được $L = Theta(loglog n)$. Như vậy $T(n) = Theta (n loglog n)$.

Ghi chú 4: Định lý thợ tương đối dài chiếc và khó khăn nhớ. Thực tế ta không độc nhất thiết buộc phải nhớ cụ thể định lý này. Hai vấn đề cần nhớ từ bỏ định lý này là: (a) gồm một công thức bao quát để ta hoàn toàn có thể tra cứu vớt và đối chiếu khi bắt buộc dùng và (b) phương thức cây đệ quy nhằm giải hệ thức truy nã hồi. Về bản chất, phương pháp cây nhị phân mới là điều cần ghi nhớ sinh hoạt đây.

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

Trong phần này chúng ta sẽ tò mò một hình thức rất khỏe khoắn để giải bí quyết đệ quy có dạng trong việc 2. Phương pháp được khuyến cáo bởi Mohamad Akra với 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 câu hỏi 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 hoàn toàn có thể tham khảo chứng tỏ của định lí này trong <2>.

Ví dụ 6: tìm 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 tìm kiếm $ ho$ vừa lòng phương trình (3): $(3/4)^ ho + (1/4)^ ho = 1$. Dễ dàng thấy giải thuật ở đây là $ ho = 1$. 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)$ hiểu được eginalignedT(n) = T(n/5) + T(7n/10) + n.endaligned

Lời giải: Ta tìm $ ho$ thỏa mãn: $(1/5)^ ho + (7/10)^ ho = 1$. Không cạnh tranh để thấy $ ho$ đã là một số nằm trong tầm $(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 bao 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 quý giá 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 giải thuật dưới dạng dãy số Fibonacci.).

Bài tập 2: áp dụng định lý thợ, tra cứu 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: áp 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: Mẫu Đơn Xin Học Hè Thcs - Đơn Xin Học Hè Tại Trường

Bài tập 1 được mang từ Jeff Erickson Notes và bài xích tập 3 mang từ Introduction lớn Algorithm, 2nd.