作者fmtshk (fmtshk)
看板Grad-ProbAsk
標題[理工] 離散_時間複雜度
時間Sun Sep 1 15:18:21 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1567322303.A.AA5.html
1F：→ JKLee: 根據你貼的定義，答案是錯的 09/01 16:33
2F：→ fmtshk: 那麼應該改成什麼才對呢？ 09/01 17:32
3F：→ JKLee: 你的想法沒有錯 09/01 17:34
4F：→ JKLee: 比較保險的做法是去翻該學校教演算法的教科書，查看big-O 09/01 17:38
5F：→ JKLee: 的定義以及有沒有類似習題(負函數的複雜度)的解答 09/01 17:38
6F：→ DLHZ: O(1)只是比較不靠近但還是符合定義吧？ 09/01 22:14
7F：→ DLHZ: 修正 我覺得應該是O(logn)才對 09/01 22:24
8F：→ frank1688: 憑印象，記得子嘉好像有說過，那個絕對值有沒有是沒有 09/02 23:13
9F：→ frank1688: 差的，只是在數學上為了嚴謹才加的，實際上在乎的只有 09/02 23:14
10F：→ frank1688: 成長率 09/02 23:14
11F：→ frank1688: 所以你看資料結構或演算法的 可能就不會寫 09/02 23:15