[理工] 時間複雜度

看板Grad-ProbAsk作者時間5年前 (2018/10/22 15:30), 編輯推噓2(2推 0噓 12→)
留言14則, 4人參與, 6年前最新討論串9/12 (看更多)
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
推
10/22 16:09, 5年前 , 1F
第一個是True，洪逸的答案打錯了
10/22 16:09, 1F
→
10/22 16:10, 5年前 , 2F
10/22 16:10, 2F
→
10/22 16:11, 5年前 , 3F
這林立宇的版本
10/22 16:11, 3F
推
10/22 17:07, 5年前 , 4F
10/22 17:07, 4F
→
10/22 17:07, 5年前 , 5F
345我覺得跟nannnnn大在這篇留言提到的情形一樣，如果把
10/22 17:07, 5F
→
10/22 17:07, 5年前 , 6F
函數取log(就是你提到的變小)比大小一定要有little-o的
10/22 17:07, 6F
→
10/22 17:07, 5年前 , 7F
關係，就是分得出絕對等級大小的關係，才能保證原函數的
10/22 17:07, 7F
→
10/22 17:07, 5年前 , 8F
大小關係是一樣的
10/22 17:07, 8F
→
10/22 17:09, 5年前 , 9F
反過來想，所以變大之後的關係不一定會跟原來關係一樣
10/22 17:09, 9F
→
10/23 08:32, 5年前 , 10F
瞭解，謝謝
10/23 08:32, 10F
→
02/05 00:31, 6年前 , 11F
4應該不對歐 取g(n)=2,f(n)為一個小於1大於0的函數
02/05 00:31, 11F
→
02/05 00:31, 6年前 , 12F
f取log之後直接就可以負到天荒地老 不符合大O的定義
02/05 00:31, 12F
→
02/05 00:33, 6年前 , 13F
取log跟次方應該都要考慮一下有沒有例外狀況
02/05 00:33, 13F
→
02/05 00:33, 6年前 , 14F
覺得是TFTFF吧
02/05 00:33, 14F
‣ 更多 gpsmelody07 的文章
文章代碼(AID): #1RpNo5y9 (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 9 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 gpsmelody07 的文章
文章代碼(AID): #1RpNo5y9 (Grad-ProbAsk)