[理工] 時間複雜度

[gpsmelody07 ()]

http://i.imgur.com/kNrTv2u.jpg

問選項(1)為什麼是False

另外想問(3)(4)(5)
常見的運算中，是不是只有取指數時不一定會維持原本的symbol，其他大多數運算都會維持？(如34取根號與lg都沒變)

http://i.imgur.com/PK0HFJY.jpg

我知道O(f(n))+θ(f(n))=θ(f(n))
但這意味著O(f(n))+θ(f(n))=O(f(n))是錯的嗎？
因為題目只問對錯，沒要找最適當的symbol

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.18.82
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1540193413.A.F09.html
推 wei12f8158: 第一個是True，洪逸的答案打錯了
→ wei12f8158:  https://i.imgur.com/p2rJI97.jpg
→ wei12f8158: 這林立宇的版本
推 skyHuan: #1Rjqdh3O (Grad-ProbAsk)
→ skyHuan: 345我覺得跟nannnnn大在這篇留言提到的情形一樣，如果把
→ skyHuan: 函數取log(就是你提到的變小)比大小一定要有little-o的
→ skyHuan: 關係，就是分得出絕對等級大小的關係，才能保證原函數的
→ skyHuan: 大小關係是一樣的
→ skyHuan: 反過來想，所以變大之後的關係不一定會跟原來關係一樣
→ gpsmelody07: 瞭解，謝謝
→ GeniusPuddin: 4應該不對歐 取g(n)=2,f(n)為一個小於1大於0的函數
→ GeniusPuddin: f取log之後直接就可以負到天荒地老 不符合大O的定義
→ GeniusPuddin: 取log跟次方應該都要考慮一下有沒有例外狀況
→ GeniusPuddin: 覺得是TFTFF吧