作者hanhancute (Hanhan)
看板Grad-ProbAsk
標題[理工] 台大101 複雜度
時間Fri Jan 11 15:32:03 2019
https://imgur.com/pnHtazd
如圖
藍字是我的想法
想知道哪裡出了問題~
幫忙解惑一下 謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.8.161.124
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547191925.A.85B.html
1F：→ z3588191: 內層應該是log(i) 所以總共是log(1)+log(2)+...+log(n) 01/11 15:36
2F：→ z3588191: =log(n!)=O(nlogn) 01/11 15:37
3F：→ z3588191: ㄚㄚ我看錯了 等等拍給你看 01/11 15:41
5F：→ z3588191: 如果沒有那個goo的話 答案的確是O(nlogn) 01/11 15:46
6F：→ z3588191: 但有goo就不一樣惹 01/11 15:47
7F：推 jojoboy0115: 注意看第二個for loop的中止條件...會無限迴圈吧... 01/11 16:32
8F：→ z3588191: int除法只取整數部分喔 像3/2=1,1/2=0 不會無限迴圈喔 01/11 17:26
9F：→ z3588191: 幹 我又看錯了 是會無限沒錯 抱歉QQ 01/11 17:27
10F：→ z3588191: 我真的會害人不淺耶 還是繼續潛水好惹 01/11 17:28
11F：→ hanhancute: 第二個 for loop改成>=1 就不會無窮迴圈了吧 01/11 17:33
12F：→ hanhancute: 那這樣答案是我寫的那樣嗎.. 01/11 17:35
13F：推 nannnnn: 如果不會無窮 應該也是z大寫的那樣 01/11 17:50
14F：推 jojoboy0115: z大別別，因為我也是跟原po推出一樣的複雜度@@，可以 01/11 18:26
15F：→ jojoboy0115: 再把過程列詳細一點嗎？不知道哪邊沒有考慮到... 01/11 18:26
17F：推 kobebset105: 解答錯了 答案是nlogn 01/11 19:45
18F：→ z3588191: e大寫的很詳細了 答案的確是n^2 01/11 20:20
先謝謝各位大大 E大的算式大概知道 只是這樣有考慮到goo那個function嗎
※ 編輯: hanhancute (36.239.45.85), 01/11/2019 20:37:26
※ 編輯: hanhancute (36.239.45.85), 01/11/2019 20:38:09
19F：推 eggy1018: 有喔 我寫的執行次數就是直接考慮內圈加執行了，想法比 01/11 21:57
20F：→ eggy1018: 較像是直接思考執行幾次，不知道這樣說你聽不聽得懂QQ 01/11 21:57
隔一點時間回來看 有點fu了~ 謝謝e大!
※ 編輯: hanhancute (36.239.45.85), 01/11/2019 23:50:39
21F：推 skyHuan: 答案不是nlogn嗎 01/12 00:00
22F：推 skyHuan: 喔喔喔是n^2沒錯，一直算錯QQ 01/12 00:03