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

Trong bài này, bọn họ tìm hiểu một vài cách giải cách làm truy hồi mà bọn họ hay gặp mặt trong so sánh thuật toán. Tương đối nhiều hệ thức tróc nã hồi xuất hiện trong phân tích thuật toán rất có thể quy được về một trong những hai câu hỏi tổng quát lác sau:

Bài toán 1: Giải hệ thức tróc nã hồi: eginaligned T(n) = aT(fracnb) + f(n) qquad (1)endaligned trong các 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 truy hỏi 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 bác này, họ sẽ tò mò 3 cách thức giải. Mỗi cách thức có ưu với nhược điểm riêng rẽ của nó. Ta bước đầu với cách thức đơn giản nhất.

1. Cách 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.

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ỉ đơn giản và dễ dàng giải hệ thức truy tìm 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 kiếm 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 cực hiếm đầu tiên, ta thấy:eginaligned T(2) = 3, T(3) = 7, T(4) = 15, ldots endalignedKhông khó để nhận thấy 3 quý hiếm đầu toại ý quy luật: $T(2) = 2^2-1$, $T(3) = 2^3-1$, $T(4) = 2^4-1$. Vị đó, ta có thể dự đoán $ T(n) = 2^n -1$.

Chứng minh: Theo đưa thiết quy nạp, ta tất cả $T(n-1) = 2^n-1-1$. Vị đó: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ử áp dụng cho bài toán khó hơn

Ví dụ 2: search 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à 1 trong những hằng số $c$ nào đó (ví dụ 2, 3 hay 5). Với từng hằng số, lúc giải hệ thức, ta 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 lấy ví dụ như 2? thực chất ta chỉ cân nhắc giá trị tiệm cận của $T(n)$ theo thay đổi $n$ chứ chưa phải một biểu thức đúng chuẩn của $n$. Xem lại bài xích tiệm cận trên đây.

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

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

Giờ ta thử chứng tỏ $T(n) leq a nlog n$. Điểm chủ công ở đó 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é nhỏ nhất của $n$ để tham dự đ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 trả sử $ n geq 2^2/a $. Như vậy, dự kiến của chúng ta là đúng.

Ghi chú 2: dường như như ta sẽ “tuỳ tiện” đưa sử $n geq 2^2/a$. Thực ra đây ko phải là 1 trong những giả sử tuỳ tiện. Chúng ta 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 khái niệm của big-O.

Bây giờ họ thử minh chứng cận dưới $T(n) geq bnlog n$ bởi quy nạp với $b$ là 1 trong những 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 và 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 chất ta đã chứng minh $T(n) = O(n log n)$, và vì $nlog n = O(nsqrtn)$ bắt buộc hiển nhiên $T(n) = O(nsqrtn)$. Xem lại đặc thù 1 của bài xích 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à = và sqrtnT(sqrtn) + n \& leq và sqrtncdot asqrtn loglog sqrtn +n \& = & a nloglog n -a n + n \& leq và a n loglog nendarray

khi $a geq 2$. Tiếng 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 \& = và 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à 1 trong những công thay giúp ta giải những hệ thức tầm nã hồi bao gồm dạng trong bài toán 1. Định lý nhiều năm và cạnh tranh nhớ với theo mình độc giả cũng không đề nghị nhớ làm gì. Chỉ việc 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 hoàn toàn có thể thì chỉ việc nhớ phương thức chứng minh định lý.


Định lý thợ
: mang đến hệ thức truy nã hồi:eginaligned T(n) = aT(fracnb) + f(n)endalignedNếu $ af(n/b) = kappa f(n)$ cùng với $ kappa giả dụ $ af(n/b) = K f(n)$ cùng 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: bọn họ sử dụng phương pháp cây đệ quy. Cây đệ quy gồm nút gốc có mức giá trị $ f(n)$ với $ a$ nút con. Từng nút bé của nút cội sẽ là nơi bắt đầu của một cây cho hàm đệ quy $ T(n/b)$. Như vậy, nghỉ ngơi độ sâu sản phẩm $ i$, cực hiếm của hàm của những nút là $ f(n/b^i)$. Coi minh hoạ trong hình 1.

*

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 cắt 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Ở đây $ L$ là độ sâu của cây đệ quy. Dễ dàng 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$ giảm sút $b$ lần. Xét ngôi trường hợp:

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

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

Ví dụ 3: tra cứu 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 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: search tiệm cận của $T(n)$ hiểu được $T(n) = 3T(n/2) + n$.

Lời giải: do $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 thực hiện 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: tìm tiệm cận của $T(n)$ hiểu được $T(n) = sqrtnT(sqrtn) + n$.

Lời giải: vày dạng của phương trình đệ quy này sẽ không giống với dạng vào định lý thợ, ta không thể vận dụng công thức tổng thể của định lý thợ. Mặc dù nhiên, ta có thể áp dụng trực tiếp cách thức cây đệ quy. Chú ý vào cây nhị phân, ta thấy tổng giá trị mỗi nút là $n$. Bởi đó, $T(n) = sum_i=1^L n$ với chiều cao cây $L$. Không cực nhọc để 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 chiếc và nặng nề nhớ. Thực chất ta không nhất thiết nên 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 tổng thể để ta rất có thể tra cứu và so sánh khi cần dùng cùng (b) phương thức cây đệ quy nhằm giải hệ thức truy hồi. Về bạn dạng chất, phương thức cây nhị phân mới là điều cần ghi nhớ ở đây.

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

Trong phần này chúng ta sẽ mày mò một hình thức rất mạnh mẽ để giải công thức đệ quy gồm dạng trong việc 2. 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à những hằng số, giải mã của việc 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 chứng minh của định lí này trong <2>.

Ví dụ 6: search 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$ vừa lòng phương trình (3): $(3/4)^ ho + (1/4)^ ho = 1$. Dễ thấy giải mã ở đấy là $ ho = 1$. Bởi đó, 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)$ biết rằng eginalignedT(n) = T(n/5) + T(7n/10) + n.endaligned

Lời giải: Ta search $ ho$ thỏa mãn: $(1/5)^ ho + (7/10)^ ho = 1$. Không khó để thấy $ ho$ đã là một số nằm trong tầm $(0,1)$. (Ta hoàn toàn có thể sử áp 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, 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ý hiếm 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 dãy số Fibonacci.).

Bài tập 2: sử dụng định lý thợ, kiếm tì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: thực hiện cây đệ quy hoặc phương pháp kinh điển để 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: Nội Dung Cơ Bản Của Cương Lĩnh Chính Trị Đầu Tiên Của Đảng, Cộng Sản Việt Nam

Bài tập 1 được mang từ Jeff Erickson Notes và bài tập 3 đem từ Introduction to Algorithm, 2nd.