[理工] [DS]-時間複雜度
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)(n+4)得
T(n+1)/(n+4) = 2n+1/(n+1)(n+4) + T(n)/(n+1)
此時假如當n很大時 或者是說他的複雜度小於下列式子
得T(n+1)/(n+1) = 1/n + T(n)/n
令An = T(n)/n 得A(n+1) = 1/n + An
解得An = O(log n)
所以T(n)=O(n log n)
不知道可不不可這樣証 可以的話 快速排序的平均case複雜度也可以這樣算...
請高手指導!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.127.208.96
推
01/10 01:01, , 1F
01/10 01:01, 1F
討論串 (同標題文章)