bài bác 2: Giải hệ thức truy nã hồi

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

Bài toán 1: Giải hệ thức truy nã hồi: eginaligned T(n) = aT(fracnb) + f(n) qquad (1)endaligned trong số đó $a,b$ là những hằng số dương.

Bạn đang xem: 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à những hằng số dương.

Trong bài bác này, họ sẽ mày mò 3 phương 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 bắt đầu với phương pháp đơn giản nhất.

1. Phương thức đoán

Đây chắc hẳn rằng là phương thức mà bọn họ thường tuyệt nghĩ tới khi phát hiện một hệ thức truy hỏi hồi.

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

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

Ví dụ 1 search 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 nặng nề để nhận biết 3 cực hiếm đầu vừa ý quy luật: $T(2) = 2^2-1$, $T(3) = 2^3-1$, $T(4) = 2^4-1$. Vì chưng đó, 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$. Do đó:eginaligned T(n) = 2T(n-1) + 1 = 2(2^n-1-1) + 1 = 2^n -1endalignedĐây là dpcm.

Bây giờ chúng ta thử áp dụng cho việc khó hơn

Ví dụ 2: kiếm tìm 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 $T(1)$ là 1 hằng số $c$ nào đó (ví dụ 2, 3 giỏi 5). Với từng hằng số, lúc giải hệ thức, ta tìm được một $T(n)$ khác nhau. Vì thế 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ỉ để ý đến giá trị tiệm cận của $T(n)$ theo đổi mới $n$ chứ không phải một biểu thức đúng đắn 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ó thể hỏi vì sao lại đoán $O(nlog n)$; thực tế ở đây ta cứ lựa chọn bừa một biểu thức mà ta cảm thấy hợp lý; ráng vào đó, bạn 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 lõi ở đây 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ỏ xíu nhất của $n$ để tham 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 đưa 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ư ta sẽ “tuỳ tiện” giả sử $n geq 2^2/a$. Thực chất đây ko phải là một giả sử tuỳ tiện. Bạn có thể giả sử $n$ “lớn tuỳ ý”. Để hiểu lý do ta lại được phép đưa sử như vậy, bạn phải xem lại định nghĩa của big-O.

Bây giờ họ thử chứng minh cận dưới $T(n) geq bnlog n$ bằng 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à ko thể xảy ra vì với mọi cực hiếm của hằng số $b$, luôn tồn tại $n$ đủ lớn để $ fracb2 nlog n

Ghi chú 3: thực tế ta đã chứng tỏ $T(n) = O(n log n)$, và vày $nlog n = O(nsqrtn)$ bắt buộc hiển nhiên $T(n) = O(nsqrtn)$. Coi lại đặc điểm 1 của bài bác tiệm cận.

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

eginarray lcl T(n) 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ỉ cần 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 & sqrtncdot bsqrtn loglog sqrtn +n \& = & b nloglog n -b n + n \& geq & b n loglog n qquad mboxnếu b leq 1endarray

Do đó, ta có thể kết luận $T(n) = Theta(nloglog n)$.

Định lý thợ

Định lý thợ (master theorem) là 1 công chũm giúp ta giải các hệ thức tầm nã hồi có dạng trong câu hỏi 1. Định lý lâu năm và nặng nề nhớ và theo mình bạn đọc cũng không đề xuất nhớ làm gì. Chỉ cần nhớ dạng việc mà định lý này có thể áp dụng để giải. Nếu có thể thì chỉ việc nhớ phương thức 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)$ với $ kappa nếu như $ af(n/b) = K f(n)$ với $ K > 1$, ta bao gồm $ 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: chúng ta sử dụng phương thức cây đệ quy. Cây đệ quy có nút gốc có mức giá trị $ f(n)$ với $ a$ nút con. Mỗi nút nhỏ của nút cội sẽ là gốc của một cây đến hàm đệ quy $ T(n/b)$. Như vậy, sinh hoạt độ sâu vật dụng $ i$, cực hiếm của hàm của các nút là $ f(n/b^i)$. Xem minh hoạ trong hình 1.

*

Hình 1: Minh hoạ cây đệ quy giải hệ thức truy hồi vào đị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ễ thấy, $ L = log_b n$ do mỗi lần đi xuống sâu thêm 1 mức của cây đệ quy, quý giá 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 có $ a^if(n/b^i) = f(n)$. Điều này có nghĩa là tổng quý giá tại mỗi mức của cây là $f(n)$. Vị cây bao gồm $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ị $af(n/b)leq a f(n)$ vì $f(.)$ là 1 hàm đối chọi điệu tăng theo $n$ khi $n$ đủ lớn.

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

Ví dụ 3: kiếm tìm tiệm cận của $T(n)$ biết rằng $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 có $T(n) = O(f(n)log n) = O(nlog n)$.

Trong ví dụ 3, ta cũng có thể dùng phương pháp trong phương trình (1) nhằm tính. Nạ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 kiếm tiệm cận của $T(n)$ biết rằng $T(n) = 3T(n/2) + n$.

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

Nếu áp dụng công thức (1) trong lấy ví dụ như 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: kiếm tìm tiệm cận của $T(n)$ biết rằng $T(n) = sqrtnT(sqrtn) + n$.

Lời giải: do dạng của phương trình đệ quy này sẽ không giống cùng với dạng vào định lý thợ, ta không thể áp 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. Quan sát vào cây nhị phân, ta thấy tổng giá trị mỗi mức là $n$. Bởi đó, $T(n) = sum_i=1^L n$ với độ cao cây $L$. Không khó khăn để 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)$. Bởi vậy $T(n) = Theta (n loglog n)$.

Ghi chú 4: Định lý thợ khá dài mẫu và cực nhọc nhớ. Thực ra ta không nhất thiết yêu cầu nhớ cụ thể định lý này. Hai điều cần nhớ tự định lý này là: (a) bao gồm một công thức tổng quát để ta có thể tra cứu vãn và đối chiếu khi đề xuất dùng cùng (b) cách thức cây đệ quy nhằm giải hệ thức truy hỏi hồi. Về bản chất, cách thức cây nhị phân mới là vấn đề cần ghi nhớ ngơi nghỉ đây.

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

Trong phần này chúng ta sẽ khám phá một phương pháp rất mạnh khỏe để giải phương pháp đệ quy tất cả dạng trong vấn đề 2. Phương pháp được khuyến nghị bởi Mohamad Akra và Louay Bazzi năm 1998. Với đk $k,a_i,b_i$ là các hằng số, giải mã của vấn đề 2 tất cả 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 vào <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 $ ho$ thỏa mãn phương trình (3): $(3/4)^ ho + (1/4)^ ho = 1$. Dễ thấy giải thuật ở đấy là $ ho = 1$. Do đó, ta có:eginaligned T(n) = Theta(n(1 + int_1^n fracuu^2du)) = O(nlog n)endaligned

Ví dụ 7: kiếm 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 khó để thấy $ ho$ sẽ là một trong những nằm trong vòng $(0,1)$. (Ta hoàn toàn có thể sử thực hiện wolframalpha để 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 giá trị 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 giải thuật dưới dạng dãy số Fibonacci.).

Bài tập 2: sử dụng định lý thợ, search 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: thực hiện cây đệ quy hoặc phương pháp kinh khủng để tìm quý giá 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: Lá Tía Tô Chữa Bệnh Gì? 10 Công Dụng Lá Tía Tô Tươi Uống Nước Lá Tía Tô Có Tác Dụng Gì

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