[理工] 演算法 時間複雜度
洪捷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
推
07/26 15:22, , 1F
07/26 15:22, 1F
推
07/26 16:26, , 2F
07/26 16:26, 2F
→
07/26 16:26, , 3F
07/26 16:26, 3F
→
07/26 16:26, , 4F
07/26 16:26, 4F
→
07/26 16:26, , 5F
07/26 16:26, 5F
推
07/26 17:23, , 6F
07/26 17:23, 6F
→
07/26 17:23, , 7F
07/26 17:23, 7F
→
07/26 17:23, , 8F
07/26 17:23, 8F
討論串 (同標題文章)
