[理工] 時間複雜度

作者: gpsmelody07 (YC)   2018-10-22 15:30:10
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
作者: wei12f8158 (WEI)   2018-10-22 16:09:00
第一個是True,洪逸的答案打錯了https://i.imgur.com/p2rJI97.jpg這林立宇的版本
作者: skyHuan (Huan)   2018-10-22 17:07:00
#1Rjqdh3O (Grad-ProbAsk)345我覺得跟nannnnn大在這篇留言提到的情形一樣,如果把函數取log(就是你提到的變小)比大小一定要有little-o的關係,就是分得出絕對等級大小的關係,才能保證原函數的大小關係是一樣的反過來想,所以變大之後的關係不一定會跟原來關係一樣
作者: gpsmelody07 (YC)   2018-10-23 08:32:00
瞭解,謝謝

Links booklink

Contact Us: admin [ a t ] ucptt.com