[理工] 離散_時間複雜度

看板Grad-ProbAsk作者 (fmtshk)時間4年前 (2019/09/01 15:18), 編輯推噓0(0011)
留言11則, 4人參與, 4年前最新討論串1/1
https://i.imgur.com/yNqc87H.jpg
https://i.imgur.com/ORQuyyY.jpg
請問黃線處,-log n = O(1)應該怎麼解釋好呢? 記得是時間複雜度為負的時候就是常數? 但從那個定義,看起來是要開絕對值的意思嗎? 開完就變正log n ? 觀念有點模糊,求高端教一下@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.215.43 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1567322303.A.AA5.html

09/01 16:33, 4年前 , 1F
根據你貼的定義,答案是錯的
09/01 16:33, 1F

09/01 17:32, 4年前 , 2F
那麼應該改成什麼才對呢?
09/01 17:32, 2F

09/01 17:34, 4年前 , 3F
你的想法沒有錯
09/01 17:34, 3F

09/01 17:38, 4年前 , 4F
比較保險的做法是去翻該學校教演算法的教科書,查看big-O
09/01 17:38, 4F

09/01 17:38, 4年前 , 5F
的定義以及有沒有類似習題(負函數的複雜度)的解答
09/01 17:38, 5F

09/01 22:14, 4年前 , 6F
O(1)只是比較不靠近但還是符合定義吧?
09/01 22:14, 6F

09/01 22:24, 4年前 , 7F
修正 我覺得應該是O(logn)才對
09/01 22:24, 7F

09/02 23:13, 4年前 , 8F
憑印象,記得子嘉好像有說過,那個絕對值有沒有是沒有
09/02 23:13, 8F

09/02 23:14, 4年前 , 9F
差的,只是在數學上為了嚴謹才加的,實際上在乎的只有
09/02 23:14, 9F

09/02 23:14, 4年前 , 10F
成長率
09/02 23:14, 10F

09/02 23:15, 4年前 , 11F
所以你看資料結構或演算法的 可能就不會寫
09/02 23:15, 11F
文章代碼(AID): #1TQt2_gb (Grad-ProbAsk)