作者newpuma (还很新)
看板Grad-ProbAsk
标题[理工] 演算法 时间复杂度
时间Tue Jul 26 15:05:24 2016
洪捷1-9 98年交大资工
We abuse the "+" operator with the asymptotic notations. For example, we may s
ay that the total time for an algorithm is O(n)+θ(n). Which two of following
statements are true.
c.)O(nlogn)+θ(nlogn)=O(nlogn)
答案是说这个选项是FALSE，为什麽呢？
其中
b.)O(n^2)+θ(n^2)=θ(n^2)
这个选项是TRUE
那麽也肯定O(nlogn)+θ(nlogn)=θ(nlogn)
竟然满足这个函式被bound在nlog，不也代表是O(nlogn)吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.136.51.18
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1469516726.A.027.html
1F：推 snailpon: Which "two" 07/26 15:22
2F：推 k2shouai: 看定义 θ(夹集) is more precise than O(upper bound) 07/26 16:26
4F：→ ken52011219: 图大概就可以知道它的直域 在四种可能中有三种共同 07/26 16:26
5F：→ ken52011219: 落在theta剩余一种不可能发生 07/26 16:26
6F：推 hut326521: 假设取f(n)=n^2 则系塔(nlogn)符合但O(nlogn)不符合 07/26 17:23
7F：→ hut326521: 若是往下取则有下限 系塔(nlogn)跟O(nlogn)都会符合 07/26 17:23
8F：→ hut326521: 所以相加会是系塔(nlogn) 07/26 17:23