Re: [問題] 兩題複雜度求解

[FRAXIS (喔喔)]

※ 引述《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