[理工] 台大101 複雜度 hanhancute PTT批踢踢實業坊

作者: hanhancute (Hanhan) 2019-01-11 15:32:03

https://imgur.com/pnHtazd
如圖
藍字是我的想法
想知道哪裡出了問題~
幫忙解惑一下謝謝!

作者: z3588191 2019-01-11 15:36:00

內層應該是log(i) 所以總共是log(1)+log(2)+...+log(n)=log(n!)=O(nlogn)ㄚㄚ我看錯了等等拍給你看https://imgur.com/a/G7g3lo1如果沒有那個goo的話答案的確是O(nlogn)但有goo就不一樣惹

作者: jojoboy0115 (jojo) 2019-01-11 16:32:00

注意看第二個for loop的中止條件...會無限迴圈吧...

作者: z3588191 2019-01-11 17:26:00

int除法只取整數部分喔像3/2=1,1/2=0 不會無限迴圈喔幹我又看錯了是會無限沒錯抱歉QQ我真的會害人不淺耶還是繼續潛水好惹

作者: hanhancute (Hanhan) 2019-01-11 17:33:00

第二個 for loop改成>=1 就不會無窮迴圈了吧那這樣答案是我寫的那樣嗎..

作者: nannnnn (nannnnn) 2019-01-11 17:50:00

如果不會無窮應該也是z大寫的那樣

作者: jojoboy0115 (jojo) 2019-01-11 18:26:00

z大別別，因為我也是跟原po推出一樣的複雜度@@，可以再把過程列詳細一點嗎？不知道哪邊沒有考慮到...

作者: eggy1018 (ç¾…å¯†æèˆ‡è±¬éŽå¤œ) 2019-01-11 18:46:00

作者: kobebset105 (小小小妹) 2019-01-11 19:45:00

解答錯了答案是nlogn

作者: z3588191 2019-01-11 20:20:00

e大寫的很詳細了答案的確是n^2

作者: eggy1018 (ç¾…å¯†æèˆ‡è±¬éŽå¤œ) 2019-01-11 21:57:00

有喔我寫的執行次數就是直接考慮內圈加執行了，想法比較像是直接思考執行幾次，不知道這樣說你聽不聽得懂QQ

作者: skyHuan (Huan) 2019-01-12 00:00:00

答案不是nlogn嗎喔喔喔是n^2沒錯，一直算錯QQhttps://i.imgur.com/7PQHKvx.jpg

繼續閱讀