如何證明 T(n) = 2T( |_n/2_| + 17 ) + n 的複雜度 O(n*log n) ?
我的想法:
1. Guess T(n) = O(n*log n) then Assume T(n)<= c * nlog n
2. 代入原式得
T(n) <= 2*c* (|_n/2_| + 17)*log( |_n/2_| + 17 ) + n
= c*(n+34)log( |_n/2_| + 17 ) + n
接下來不會了.....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.215.97