作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [DS]-时间复杂度
时间Sun Jan 31 10:35:54 2010
※ 引述《NOtWorThy (分子小於64)》之铭言：
: O(n*n) + theta(n*n) = theta(n*n) //最佳表示法
: theta(n*n) + omega(n*n) = omega(n*n)
: theta(n*n) + O(n*n*logn) = O(n*n*logn)
: 有高手可以解释一下吗??
: 完全看不懂 为何如此
: 感激不尽~!
我遇到这种题目，都是把上下限分开来看
然後上限和下限分别运算（用集合的角度），最後再把两者的结果合并
举例第二题
theta(n*n) + omega(n*n) = ?
上限 O(n*n) + 无界 = 无界
下限 omega(n*n) + omega(n*n) = omega(n*n)
所以答案就是omega(n*n)
第三题
theta(n*n) + O(n*n*logn) =
上限 O(n*n) + O(n*n*logn) = O(n*n*logn)
下限 omega(n*n) + 无界 = omega(n*n)
所以答案是O(n*n*logn) and omega(n*n)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 wwf90322:请问一下那第一小题怎麽看? O(n*n)+theta(n*n)=O(n*n)? 01/31 11:04
2F：→ polomoss:O+theta = theta 01/31 11:31
※ 编辑: FRAXIS 来自: 140.119.162.50 (01/31 18:38)
3F：→ FRAXIS:第三题写错了 修改一下 01/31 18:39
4F：推 NOtWorThy:谢谢你~~!! 那像 O(f(n)) + omega(f(n)) 这种呢 01/31 19:57
5F：→ FRAXIS:变成omega(f(n))吧 我想 01/31 21:00