Re: [問題] 計算時間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者scwg ( )時間13年前 (2011/11/07 23:59)推噓2(2推 0噓 2→)留言4則, 3人參與討論串3/4 (看更多)
※ 引述《lf963 ()》之銘言：
: 想請問三題關於時間複雜度的計算
: 第一題 證明 http://0rz.tw/tPSN9
: 我知道指數成長會比lgn快 但是考試出來應該不能只寫這句吧
: 不知道有沒有比較嚴謹的證法
如果題目就是要證明 lhs = Θ(n^{1.001}), 那應該是要用 Θ(.) 的定義展開
找出 n0, c0, c1 使得
forall n > n0, c0 * n^{1.001} <= n^{1.001} + n lg n
<= c1 * n^{1.001}
: 第二題 求upper and lower bound as tigth as possible
: http://0rz.tw/TLpdn
: 第一行是題目 第二行是小弟的想法 將每個平方項展開後
: 算出的答案是系塔(n^3) 不知道對不對
看起來像是對的, 不過可以試試 master theorem
: 第三題 求upper and lower bound as tigth as possible
: http://0rz.tw/Hp8ny
: 第一行是題目 第二行是小弟的想法 最後算出是 1/lgnlgn
: 但始終感覺怪怪的 1/lgnlgn 跑的速度不是會非常快嗎
: 不知有沒有算錯
從
T(2^{1/m}) = T(2^{1/m} - 2) + m
到
S(m) = S(m - 2) + m
這行錯的. 如果 S(m) = T(2^{1/m) 那麼
S(m-2) = T(2^{1/(m-2)}) != T(2^{1/m} - 2)
這題應該也是 master theorem..
: 順便問一下第二和第三題 一直遞迴展開的最後一項是要寫0好還是1好
: 謝謝各位
照著定義寫. T(0) 是多少就寫多少.
--
A man may die, countries may rise and fall, but an idea lives on.
- John F. Kennedy
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.36.232.45
推
11/08 00:21, , 1F
11/08 00:21, 1F
→
11/08 04:50, , 2F
11/08 04:50, 2F
→
11/08 13:36, , 3F
11/08 13:36, 3F
推
11/08 21:42, , 4F
11/08 21:42, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12