[理工] 演算法 時間複雜度

[newpuma (還很新)]

洪捷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://www.ptt.cc/bbs/Grad-ProbAsk/M.1469516726.A.027.html
推 snailpon: Which "two"
推 k2shouai: 看定義 θ(夾集) is more precise than O(upper bound)
→ ken52011219:  http://i.imgur.com/tdwUApc.jpg  把定義寫出來並畫
→ ken52011219: 圖大概就可以知道它的直域 在四種可能中有三種共同
→ ken52011219: 落在theta剩餘一種不可能發生
推 hut326521: 假設取f(n)=n^2 則係塔(nlogn)符合但O(nlogn)不符合
→ hut326521: 若是往下取則有下限 係塔(nlogn)跟O(nlogn)都會符合
→ hut326521: 所以相加會是係塔(nlogn)