[理工] 台大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

继续阅读