作者fish0835 (无用之人)
看板Grad-ProbAsk
标题Re: [理工] [资结]-复杂度分析
时间Mon Nov 2 01:32:34 2009
※ 引述《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