Research Space for Linear Algebra & Discrete Mathematics
令 n=2^k, T(2^k) = 2T(2^(k-1)) + klog2= 2( 2T(2^(k-2)) + (k-1)log2) + klog2= (2^2)T(2^(k-2)) + 2(k-1)log2 + klog2= ...= (2^k)T(1)+(log2)Σ[(2^r)*(k-r)], r=0,...,k-1= nT(1) + (log2)(kΣ(2^r) - Σr(2^r))= nT(1) + (log2)(k((2^k)-1) - Σr(2^r))= nT(1) + (log2)(nlgn - lgn - Σr(2^r))因為 Σr(x^r) (r=0,...,k-1)= [-k(x^k)+kx^(k+1)+x-x^(k+1)]/(1-x)^2 => Σr(2^r) = (2^k)(k-2)+2 = n(lgn-2)+2=> T(n) = nT(1) + (log2)(nlgn-lgn-(n(lgn-2)+2))= nT(1) + (log2)(2n-lgn-2)Note: 若改成 T(n)=2T(n/2)+lgn, 假設T(1)=1=> T(n) = 3n-lgn-2
原來不要合併就可以求出了..感謝你~
張貼留言
2 則留言:
令 n=2^k, T(2^k) = 2T(2^(k-1)) + klog2
= 2( 2T(2^(k-2)) + (k-1)log2) + klog2
= (2^2)T(2^(k-2)) + 2(k-1)log2 + klog2
= ...
= (2^k)T(1)+(log2)Σ[(2^r)*(k-r)], r=0,...,k-1
= nT(1) + (log2)(kΣ(2^r) - Σr(2^r))
= nT(1) + (log2)(k((2^k)-1) - Σr(2^r))
= nT(1) + (log2)(nlgn - lgn - Σr(2^r))
因為 Σr(x^r) (r=0,...,k-1)
= [-k(x^k)+kx^(k+1)+x-x^(k+1)]/(1-x)^2
=> Σr(2^r) = (2^k)(k-2)+2 = n(lgn-2)+2
=> T(n) = nT(1) + (log2)(nlgn-lgn-(n(lgn-2)+2))
= nT(1) + (log2)(2n-lgn-2)
Note: 若改成 T(n)=2T(n/2)+lgn, 假設T(1)=1
=> T(n) = 3n-lgn-2
原來不要合併就可以求出了..
感謝你~
張貼留言