作者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/cn.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