作者luckyburgess (the one)
看板Grad-ProbAsk
標題[理工] [資結]-複雜度分析
時間Sun Nov 1 22:04:11 2009
題目:T( n ) = T(sqrt( n )) + log n
T(n)=?
請問這一題可以用master 定理去解嗎??
又或是該怎麼解呢??
感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.134.213.201
1F：推 FRAXIS:log n + (log n)/2 + (log n)/4 + ... 11/01 22:17
2F：推 polomoss:令 n = 2^(2^k) 11/01 22:21
3F：推 windysoul:把sqrt(n)看成n的二分之一次方會比較好做 11/02 01:01
4F：→ windysoul:然後這題不太能用master 用遞迴下去做就好 11/02 01:04
5F：→ windysoul:說錯 是展開代入@@ 11/02 01:10