作者gpsmelody07 ()
看板Grad-ProbAsk
標題[理工] 時間複雜度
時間Mon Oct 22 15:30:10 2018
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1540193413.A.F09.html
1F：推 wei12f8158: 第一個是True，洪逸的答案打錯了 10/22 16:09
3F：→ wei12f8158: 這林立宇的版本 10/22 16:11
5F：→ skyHuan: 345我覺得跟nannnnn大在這篇留言提到的情形一樣，如果把 10/22 17:07
6F：→ skyHuan: 函數取log(就是你提到的變小)比大小一定要有little-o的 10/22 17:07
7F：→ skyHuan: 關係，就是分得出絕對等級大小的關係，才能保證原函數的 10/22 17:07
8F：→ skyHuan: 大小關係是一樣的 10/22 17:07
9F：→ skyHuan: 反過來想，所以變大之後的關係不一定會跟原來關係一樣 10/22 17:09
10F：→ gpsmelody07: 瞭解，謝謝 10/23 08:32
11F：→ GeniusPuddin: 4應該不對歐 取g(n)=2,f(n)為一個小於1大於0的函數 02/05 00:31
12F：→ GeniusPuddin: f取log之後直接就可以負到天荒地老 不符合大O的定義 02/05 00:31
13F：→ GeniusPuddin: 取log跟次方應該都要考慮一下有沒有例外狀況 02/05 00:33
14F：→ GeniusPuddin: 覺得是TFTFF吧 02/05 00:33