作者imadog (凹呜)
看板Grad-ProbAsk
标题[理工] 资演 复杂度
时间Fri Jan 11 10:48:11 2019
请问大家
https://i.imgur.com/PEmHUln.jpg
为什麽这题答案是c?
还有这题
https://i.imgur.com/6itc59y.jpg
n^3方是因为内层平方 外层1次方 所以总共3次方吗
遇到这种判断复杂度我都超不会的 请问判断技巧是甚麽QQ谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 219.69.77.222
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1547174893.A.043.html
1F：→ imadog: 再多问一个 如果是非题问复杂度 01/11 10:54
2F：→ imadog: 例如 log n =O(n) 类似这种 01/11 10:55
3F：→ imadog: 要算true还false啊? 是upper bound 但不是tight bound 01/11 10:56
4F：→ rockieloser: (N+2)-(N-2）算常数吧 10*N*4=O(N) 01/11 11:06
5F：→ rockieloser: 平方和的公式： n(n+1)(2n+1)/6 01/11 11:08
7F：→ jojoboy0115: 技巧可以参考这篇下面sky大大的推文 01/11 11:54
8F：→ jojoboy0115: 如果为是非题就答True，因为O(n)是一个集合，也有包 01/11 11:57
9F：→ jojoboy0115: 含log(n) 01/11 11:57
10F：推 Marcolod: 14. 如果我的理解没有错~~~~第一行 O(1) 第二行O(N) 01/12 10:37
11F：→ Marcolod: 第三行O(1) 第四行只是print 所以最後看O(N) 01/12 10:37
12F：推 Marcolod: 15. 第一行是O(N) 第二行是O(N^3) 所以最後取O^3 01/12 10:39
13F：推 Marcolod: 第二行的(O^3)来自於 他是第二个回圈，所以是loop 中的 01/12 10:41
14F：→ Marcolod: loop，也就是里面N^2回圈结束了，外面再加一，所以第二 01/12 10:41
15F：→ Marcolod: 行是N(N^2+1) 01/12 10:41
16F：推 Marcolod: 啊啊 我的第二个推写错了，是O(N^3)才对啦，不好意思 01/12 10:43