[理工] 資演 複雜度

看板Grad-ProbAsk作者 (凹嗚)時間7年前 (2019/01/11 10:48), 編輯推噓5(5推 0噓 11→)
留言16則, 4人參與, 7年前最新討論串1/1
請問大家 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1547174893.A.043.html
→
01/11 10:54, 7年前 , 1F
再多問一個 如果是非題問複雜度
01/11 10:54, 1F
→
01/11 10:55, 7年前 , 2F
例如 log n =O(n) 類似這種
01/11 10:55, 2F
→
01/11 10:56, 7年前 , 3F
要算true還false啊? 是upper bound 但不是tight bound
01/11 10:56, 3F
→
01/11 11:06, 7年前 , 4F
(N+2)-(N-2）算常數吧 10*N*4=O(N)
01/11 11:06, 4F
→
01/11 11:08, 7年前 , 5F
平方和的公式： n(n+1)(2n+1)/6
01/11 11:08, 5F
推
01/11 11:54, 7年前 , 6F
01/11 11:54, 6F
→
01/11 11:54, 7年前 , 7F
技巧可以參考這篇下面sky大大的推文
01/11 11:54, 7F
→
01/11 11:57, 7年前 , 8F
如果為是非題就答True，因為O(n)是一個集合，也有包
01/11 11:57, 8F
→
01/11 11:57, 7年前 , 9F
含log(n)
01/11 11:57, 9F
推
01/12 10:37, 7年前 , 10F
14. 如果我的理解沒有錯~~~~第一行 O(1) 第二行O(N)
01/12 10:37, 10F
→
01/12 10:37, 7年前 , 11F
第三行O(1) 第四行只是print 所以最後看O(N)
01/12 10:37, 11F
推
01/12 10:39, 7年前 , 12F
15. 第一行是O(N) 第二行是O(N^3) 所以最後取O^3
01/12 10:39, 12F
推
01/12 10:41, 7年前 , 13F
第二行的(O^3)來自於 他是第二個迴圈，所以是loop 中的
01/12 10:41, 13F
→
01/12 10:41, 7年前 , 14F
loop，也就是裡面N^2迴圈結束了，外面再加一，所以第二
01/12 10:41, 14F
→
01/12 10:41, 7年前 , 15F
行是N(N^2+1)
01/12 10:41, 15F
推
01/12 10:43, 7年前 , 16F
啊啊 我的第二個推寫錯了，是O(N^3)才對啦，不好意思
01/12 10:43, 16F
‣ 更多 imadog 的文章
文章代碼(AID): #1SE0Fj13 (Grad-ProbAsk)