V. GIẢI PHƯƠNG TRÌNH ĐỆ QUY
Phuơng pháp truy hồi:
Dùng đệ quy để thay thế bất kỳ T(m) với m<n vào vế phải của PT cho đến khi m=1.
VD: Giải phương trình đệ quy:
Phuơng pháp truy hồi:
Dùng đệ quy để thay thế bất kỳ T(m) với m<n vào vế phải của PT cho đến khi m=1.
VD: Giải phương trình đệ quy:
Ta có:
![T(n) = 2T(\frac{n}{2}) + C2.n\\ =2[2T(\frac{n}{2})+ C2.\frac{n}{2}] + C2.n = 4T(\frac{n}{4}) + 2.C2.n \\ =4[2T(\frac{n}{8})+ C2.\frac{n}{4}] + C2.n = 8T(\frac{n}{8}) + 3.C2.n \\ =...\\ =2^{i}.T(\frac{n}{2^{i}}) + i.C2.n](http://s0.wp.com/latex.php?latex=T%28n%29+%3D+2T%28%5Cfrac%7Bn%7D%7B2%7D%29+%2B+C2.n%5C%5C++%3D2%5B2T%28%5Cfrac%7Bn%7D%7B2%7D%29%2B+C2.%5Cfrac%7Bn%7D%7B2%7D%5D+%2B+C2.n+%3D+4T%28%5Cfrac%7Bn%7D%7B4%7D%29+%2B+2.C2.n+%5C%5C++%3D4%5B2T%28%5Cfrac%7Bn%7D%7B8%7D%29%2B+C2.%5Cfrac%7Bn%7D%7B4%7D%5D+%2B+C2.n+%3D+8T%28%5Cfrac%7Bn%7D%7B8%7D%29+%2B+3.C2.n+%5C%5C++%3D...%5C%5C++%3D2%5E%7Bi%7D.T%28%5Cfrac%7Bn%7D%7B2%5E%7Bi%7D%7D%29+%2B+i.C2.n&bg=ffffff&fg=000&s=0 "T(n) = 2T(\frac{n}{2}) + C2.n\\ =2[2T(\frac{n}{2})+ C2.\frac{n}{2}] + C2.n = 4T(\frac{n}{4}) + 2.C2.n \\ =4[2T(\frac{n}{8})+ C2.\frac{n}{4}] + C2.n = 8T(\frac{n}{8}) + 3.C2.n \\ =...\\ =2^{i}.T(\frac{n}{2^{i}}) + i.C2.n")
Giải sử
và khi kết thúc ta có i = k.
Lại có:
Giải sử
và khi kết thúc ta có i = k.Lại có:
Phương pháp tổng quát
Chia bài toán thành a bài toán con và mỗi bài toán có kích thước n/b. Và cứ chia như vậy đến khi bài toán đủ nhỏ để giải quyết (đệ quy). Và sau khi dùng phương pháp này người ta đã chỉ ra rằng đối với phương trình đệ quy:
Ta có:
T(n) = C1 nếu n=1
Với n>1 ta có:
Chia bài toán thành a bài toán con và mỗi bài toán có kích thước n/b. Và cứ chia như vậy đến khi bài toán đủ nhỏ để giải quyết (đệ quy). Và sau khi dùng phương pháp này người ta đã chỉ ra rằng đối với phương trình đệ quy:
Ta có:
T(n) = C1 nếu n=1
Với n>1 ta có:
Xem tiếp: