資結 時間複雜度(洪逸筆記)

看板Grad-ProbAsk作者 (Huan)時間6年前 (2017/12/27 02:17), 6年前編輯推噓3(3推 0噓 6→)
留言9則, 1人參與, 6年前最新討論串1/1
看筆記的時候看到這段覺得怪怪的(右下角的最後三個) https://imgur.com/UpOiges.jpg
如果直接把這些函數取log再比大小，結果應該是這樣 https://imgur.com/mjNstRk.jpg
看到筆記有這樣的解釋(左下角的部分) https://imgur.com/mDOpcrX.jpg
有點忘記老師那時候上課是怎麼講的了 跟同學討論後覺得老師的意思應該是 先比指數再比底數，指數比較大就比較大 所以O(2^(2n))才會大於O(n^n)因為指數部分2n>n 那這樣的話O(5^n)又要怎麼比呢 照上面最後一個筆記的圖應該是在最上面那層 但O(5^n)應該要大於O(4^n)=O(2^(2n))吧(?) 不知道我的想法在哪裡出錯了 麻煩版友幫忙解答了，感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.16.135 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1514312263.A.810.html ※ 編輯: skyHuan (1.163.16.135), 12/27/2017 02:20:13 ※ 編輯: skyHuan (1.163.16.135), 12/27/2017 02:21:01
推
12/27 02:28, 6年前 , 1F
呃 應該是 2^2^n 和 n^2^n 才對，不是 2^2n
12/27 02:28, 1F
→
12/27 02:31, 6年前 , 2F
看你筆記的右邊，這個等級是”指數又指數”，不是指數等
12/27 02:31, 2F
→
12/27 02:31, 6年前 , 3F
級（ex. 5^n）
12/27 02:31, 3F
→
12/27 02:32, 6年前 , 4F
等級的判斷是看你未知數n的所在位置
12/27 02:32, 4F
所以應該是筆記抄錯了嗎？ 我們有在想是不是2^2^n跟2^2n抄錯了，後來看第三個圖的筆記後才判斷應該不是抄錯， 筆記左下的左邊有取log算，過程看起來不像2^2^n ※ 編輯: skyHuan (1.163.16.135), 12/27/2017 02:39:41
推
12/27 02:45, 6年前 , 5F
你的筆記完全寫錯
12/27 02:45, 5F
→
12/27 02:45, 6年前 , 6F
如果照你的寫法來比較nlgn和2n的話，結果會是nlgn>2n
12/27 02:45, 6F
→
12/27 02:47, 6年前 , 7F
事實上，你2^2^n左邊的寫法應該要寫lg2^2^n，解出來是2^n
12/27 02:47, 7F
→
12/27 02:47, 6年前 , 8F
，這樣才會是2^n>nlgn
12/27 02:47, 8F
推
12/27 02:50, 6年前 , 9F
這樣2^2^n的等級才會大於n^n
12/27 02:50, 9F
看來應該是筆記抄錯了 這樣原本想的(第二張圖)也沒問題了 感謝你！！！ ※ 編輯: skyHuan (1.163.16.135), 12/27/2017 02:54:38
‣ 更多 skyHuan 的文章
文章代碼(AID): #1QGf97WG (Grad-ProbAsk)