作者scwg ( )
站内Prob_Solve
标题Re: [问题] 计算时间复杂度
时间Mon Nov 7 23:59:26 2011
※ 引述《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
1F：推 lf963:那麽请问第三题 S(m)应该怎麽表示 11/08 00:21
2F：→ scwg:直接对 T() 用 master theorem, 应该连把 n 换成 m 都不需要 11/08 04:50
3F：→ lf963:T(n)=aT(n/b)+f(n) 大师不是应该长这样吗? 这题要怎用大师 11/08 13:36
4F：推 i78524:第2题长那样是不能用大师的喔... 11/08 21:42