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

看板Prob_Solve作者 (喔喔)時間14年前 (2010/06/05 06:42), 編輯推噓0(0推 0噓 0→)
留言0則, 0人參與, 最新討論串3/3 (看更多)
※ 引述《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
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C2O5QyK (Prob_Solve)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C2O5QyK (Prob_Solve)