Re: [理工] [資結]-複雜度分析
※ 引述《luckyburgess (the one)》之銘言：
: 題目:T( n ) = T(sqrt( n )) + log n
: T(n)=?
: 請問這一題可以用master 定理去解嗎??
: 又或是該怎麼解呢??
: 感謝!
Let n = 2^k
=> T( n )= T( 2^k ) = T( 2^(k/2) ) + k
Let T( 2^k ) = A( k )
=> T( 2^k ) = A( k ) = A( k/2 ) + k
by master theorem
=> A( k ) = O( k )
=> T( 2^k ) = O( k )
=> T( n ) = O( lg n )
希望能幫上忙^_^
--
請勿嘗試 "複製 -> 貼上" 紫色區塊唷！
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqg
y
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.214.45
討論串 (同標題文章)