[理工] 台大101 複雜度

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