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