作者FRAXIS (喔喔)
看板Prob_Solve
标题Re: [问题] 两题复杂度求解
时间Sat Jun 5 06:42:32 2010
※ 引述《FRAXIS (喔喔)》之铭言：
: T(n) = T(n/2) + T(n^0.5) + n
我後来想出了一个解法
从递回关系式看起来T(n) = Ω(n)
而且我们知道当F(n) = F(n/2) + T(n/3) + n时, F(n) = O(n)
又当n > 9时，n/3 > n^0.5，所以T(n) < F(n) = O(n)
因此T(n) = Θ(n)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50