求解遞迴式:T(n) = lg(n) +2T(n/4) , n為正整數,n>=2. t(2)=c (某常數).?

若題目中的 lg ( n ) 是指 log ( n ) , 即以 10 為底數, n 的對數, 則 :

Sol :

T(n) - 2*T(n/4) = log n

T( 2 * 4 ) - 2*T(2) = log ( 2 * 4 ) ..... (1)

T( 2 * 4² ) - 2*T( 2 * 4 ) = log ( 2 * 4² ) ..... (2)

T( 2 * 4³ ) - 2*T( 2 * 4² ) = log ( 2 * 4³ ) ..... (3)

T( 2 * 4⁴ ) - 2*T( 2 * 4³ ) = log ( 2 * 4⁴ ) ..... (4)

.............................

T( 2 * 4^(k-2) ) - 2*T( 2 * 4^(k-3) ) = log ( 2 * 4^(k-2) ) ..... (k-2)

T( 2 * 4^(k-1) ) - 2*T( 2 * 4^(k-2) ) = log ( 2 * 4^(k-1) ) ..... (k-1)

T( 2 * 4^k ) - 2*T( 2 * 4^(k-1) ) = log ( 2 * 4^k ) ..... (k)

將第 i 式乘以 2^( k - i ) 得 :

2^(k-1)*T( 2 * 4 ) - (2^k)T(2) = 2^(k-1)*log ( 2 * 4 ) ..... ( 1# )

2^(k-2)*T( 2 * 4² ) - 2^(k-1)*T( 2 * 4 ) = 2^(k-2)*log ( 2 * 4² ) ..... ( 2# )

2^(k-3)*T( 2 * 4³ ) - 2^(k-2)*T( 2 * 4² ) = 2^(k-3)*log ( 2 * 4³ ) ..... ( 3# )

2^(k-4)*T( 2 * 4⁴ ) - 2^(k-3)*T( 2 * 4³ ) = 2^(k-4)*log ( 2 * 4⁴ ) ..... ( 4# )

.............................

( 2² )T( 2 * 4^(k-2) ) - ( 2³ )T( 2 * 4^(k-3) ) = ( 2² )log ( 2 * 4^(k-2) ) ..... ( k-2 # )

2*T( 2 * 4^(k-1) ) - ( 2² )T( 2 * 4^(k-2) ) = 2*log ( 2 * 4^(k-1) ) ..... ( k-1 # )

T( 2 * 4^k ) - 2*T( 2 * 4^(k-1) ) = log ( 2 * 4^k ) ..... ( k# )

( 1# ) + ( 2# ) + ( 3# ) + ...... + ( k-1 # ) + ( k# ) 得 :

T( 2 * 4^k ) - (2^k)T(2)

= 2^(k-1)*log (2*4) + 2^(k-2)*log (2*4²) + 2^(k-3)*log (2*4³) + ..... + 2*log (2*4^(k-1)) + log (2*4^k)

= 2^(k-1)*log (2^3) + 2^(k-2)*log (2^5) + 2^(k-3)*log (2^7) + ..... + 2*log (2^(2k-1)) + log (2^(2k+1))

= 2^(k-1)*(3 log 2) + 2^(k-2)*(5 log 2) + 2^(k-3)*(7 log 2) + ..... + 2*( (2k-1) log 2) + ( (2k+1) log 2)

= log 2 * [ 3*2^(k-1) + 5*2^(k-2) + 7*2^(k-3) + ..... + (2k-1)*2 + (2k+1) ]

T( 2 * 4^k ) - (2^k)T(2) = log 2 * [ 3*2^(k-1) + 5*2^(k-2) + 7*2^(k-3) + ..... + (2k-1)*2 + (2k+1) ]

令 S = 3*2^(k-1) + 5*2^(k-2) + 7*2^(k-3) + 9*2^(k-4) + .....+ (2k-3)*2^2 + (2k-1)*2 + (2k+1)

則 2S = 3(2^k) + 5*2^(k-1) + 7*2^(k-2) + 9*2^(k-3) + ..... + (2k-3)*2^3 + (2k-1)*2^2 + (2k+1)*2

2S - S = 3(2^k) + [ 2*2^(k-1) + 2*2^(k-2) + 2*2^(k-3) + ..... + 2*2^2 + 2*2 ] - (2k+1)

S

= 3(2^k) - 2k - 1 + [ 2^k + 2^(k-1) + 2^(k-2) + ..... + 2^3 + 2^2 ]

= 3(2^k) - 2k - 1 + 2^2*[ 2^(k-1) - 1 ]/(2-1)

= 3(2^k) - 2k - 1 + 2^(k+1) - 4

= 3(2^k) - 2k - 1 + 2(2^k) - 4

= 5(2^k) - 2k - 5

T( 2 * 4^k ) - (2^k)T(2) = ( log 2 )S

T( 2 * 4^k ) - (2^k)c = ( log 2 )[ 5(2^k) - 2k - 5 ]

T( 2 * 4^k ) = (2^k)c + ( log 2 )[ 5(2^k) - 2k - 5 ]

Ans: T( 2 * 4^k ) = (2^k)c + ( log 2 )[ 5(2^k) - 2k - 5 ] , 其中 k 為正整數

--------------------------------------------------------------------------------------------------------

驗算 :

設 T(2) = c = 7 , k = 9

利用答案的式子 T( 2 * 4^k ) = (2^k)c + ( log 2 )[ 5(2^k) - 2k - 5 ] , 所以 :

T( 524288 ) = (2^9)7 + ( log 2 )[ 5(2^9) - 2*9 - 5 ] ≒ 4347.713

再利用 Excel 模擬遞迴式 T(n) = log n + 2*T(n/4) 如下 :

A1 儲存格輸入 2 , B1 輸入 7 ,

A2 輸入 =A1*4

再下拉到 A10 , 則 A10 的計算結果為 524288

B2 儲存格輸入 =LOG(A2)+2*B1

再下拉到 B10 , 則 B10 的計算結果約為 4347.713

故驗算無誤