討論串(共3篇) - [問題] 兩題複雜度求解 - 看板Prob_Solve

看板 [ Prob_Solve ]

討論串[問題] 兩題複雜度求解

共 3 篇文章

排序：最舊先 | 最新先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

[問題] 兩題複雜度求解

推噓3(3推 )留言6則，0人參與作者FRAXIS (喔喔)時間14年前 (2010/06/02 22:39)資訊

內容預覽:

T(n) = n^0.5 T(n^0.5) + n^0.5. 假設n = 2^2^k. T(n) = n^0.5 * (n^0.25 T(n^0.25) + n^0.25) + n^0.5. = n^(1-2^-k) T(0) + n^0.5 + n^0.75 + ..... 這邊我解不出close

(還有28個字)

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

推噓0(0推 )留言0則，0人參與作者LPH66 (-858993460)時間14年前 (2010/06/04 02:36)資訊

內容預覽:

這樣吧:. 依然令 n = 2^2^k. T(n) = 2^2^(k-1) T(2^2^(k-1)) + 2^2^(k-1). = 2^2^(k-1) [ 2^2^(k-2) T(2^2^(k-2)) + 2^2^(k-2) ] + 2^2^(k-1). = (2^2^(k-1)*2^2^(k-2)

(還有821個字)

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

推噓0(0推 )留言0則，0人參與作者FRAXIS (喔喔)時間14年前 (2010/06/05 06:42)資訊

內容預覽:

我後來想出了一個解法. 從遞迴關係式看起來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). --. ※ 發信站

首頁

尾頁