Re: [理工] [DS]-時間複雜度

[FRAXIS (喔喔)]

※ 引述《yesa315 (XD)》之銘言：
: T(n) = n + (4/n)( T(1) + T(2) +...+ T(n-1))
: 求時間複雜度
: 我把兩邊乘n 然後再代n=n+1 得兩個式子
: 然後相減得
: (n+1)T(n+1) = 2n+1 + 4T(n) + n T(n)
: 我在想在算下去就放榜了 於是..

到這邊沒問題

(n+1)T(n+1) = (n+4)T(n) + 2n+1

下一步是要同除 (n+1)(n+2)(n+3)(n+4) <- 這是Full History Recurrence的技巧

T(n+1)/(n+2)(n+3)(n+4) = T(n)/(n+1)(n+2)(n+3) + (2n+1)/(n+1)(n+2)(n+3)(n+4)

令S(n) = T(n)/(n+1)(n+2)(n+3)

S(n+1) = S(n) + (2n+1)/(n+1)(n+2)(n+3)(n+4)

解出S(n) = O(1)

T(n) = S(N) * (n+1)(n+2)(n+3) = O(n^3)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.162.50
推 polomoss:怎麼兩邊答案不同@@
推 yesa315:怎嚜跟我原本複雜度差這麼多...
推 leeheng:強