Re: [理工] [DS]-時間複雜度
※ 引述《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
推
01/10 01:28, , 1F
01/10 01:28, 1F
推
01/10 13:24, , 2F
01/10 13:24, 2F
推
02/03 11:22, , 3F
02/03 11:22, 3F
討論串 (同標題文章)