[理工] [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)(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
推 swon:OK的啊~