Được sửa bởi Admin ngày Tue Mar 01, 2011 8:34 am; sửa lần 1.
Giải phương trình đệ quy T(1) = 1, T(n) = 4 T(n/2) + n^2Tue Jun 29, 2010 9:02 pmSao thầy không gởi nhiều bài đánh giá độ phức tạp lên mạng để tụi em tham khảoTue Feb 22, 2011 3:39 pm
Re: Giải phương trình đệ quy T(1) = 1, T(n) = 4 T(n/2) + n^2Thu Mar 24, 2011 10:45 pmT(n)=3T(n/2)+n
=3[3T(n/2^2)+n/2]+n
=3^2T(n/2^2)+3n/2+n(vì 3n/2+n=5n/2=(3^2-2^2)/2^1))
=3^2[3T(n/2^3)+n/2^2]+3n/2+n.....
=3^3T(n/2^3)+9n/2^2+3n/2+n
........
=3^iT(n/2^i)+(3^i-2^i)n/2^(i-1)(I)
để bài toán đạt truơng hợp cơ sơ thì T(1)=1
=>n/2^i=1,=>i=log2(n).
thay i vào biểu thức (I) ta được T(n)=O(3^log2(n))
chúc các bạn vui vẻ.có gì thì bỏ thêm những bàiRe: Giải phương trình đệ quy T(1) = 1, T(n) = 4 T(n/2) + n^2Fri May 27, 2011 5:18 pmngoctuan05 đã viết:Thầy gởi cho em vài bài đánh giá độ phức tạp nữa để em dựa vào đó mà học
Cho T(1) = 1 giải các phương trình đệ quy sau:
1. T(n) = 4T(n/2)+n^2
2. T(n) = T(n/2) + logn
3. T(n) = 3T(n/2) + n
4. T(n) = 3T(n/2) + nlogn
5. T(n) = 9T(n/4) + n
6. T(n) = 3T(n/2) + n^2
|
|
|