資結 時間複雜度

看板Grad-ProbAsk作者 (CS)時間7年前 (2018/11/28 01:04), 7年前編輯推噓4(4推 0噓 7→)
留言11則, 4人參與, 7年前最新討論串1/2 (看更多)
http://i.imgur.com/VURxMjU.jpg
請問 這個foo(i*i) 中的i*i不是應該為「一個」整數嗎？ Big-O為什麼不是 n^2 *n ? 洪逸老師給的答案是 n^2 * n^2 *n = O(n^5) ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.126.230 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543338250.A.5D3.html
推
11/28 01:26, 7年前 , 1F
(i*i)^2 = i^2*i^2?
11/28 01:26, 1F
搞不懂 :< 所以foo要n^2 跑n次 為什麼答案不是n^3 我的想法是 這個程式跑了n次foo. 其中參數i*i=O(1). foo需要O(n^2) ※ 編輯: csuperk (111.82.126.230), 11/28/2018 01:38:20 ※ 編輯: csuperk (111.82.126.230), 11/28/2018 01:39:17 ※ 編輯: csuperk (111.82.126.230), 11/28/2018 01:40:17
推
11/28 01:43, 7年前 , 2F
題目說input放多大複雜度就是他的平方，迴圈裡面input是k
11/28 01:43, 2F
→
11/28 01:43, 7年前 , 3F
=i^2複雜度就是k^2=i^4，整個迴圈的複雜度就是1^4+2^4+..
11/28 01:43, 3F
→
11/28 01:43, 7年前 , 4F
.+n^4=O(n^5)
11/28 01:43, 4F
→
11/28 01:46, 7年前 , 5F
foo函式接收一個int的參數，這個函式的複雜度會是接收的
11/28 01:46, 5F
看懂了！謝謝你們
→
11/28 01:46, 7年前 , 6F
這個int參數的平方
11/28 01:46, 6F
※ 編輯: csuperk (111.82.126.230), 11/28/2018 07:00:25
→
11/28 12:36, 7年前 , 7F
輸入是n^2 但是處理的數字是1^2、2^2...n^2
11/28 12:36, 7F
→
11/28 12:36, 7年前 , 8F
所以還是只有n筆資料 進去做這個迴圈
11/28 12:36, 8F
→
11/28 12:37, 7年前 , 9F
感覺不太合理 又不是輸入1～n^2
11/28 12:37, 9F
推
11/28 13:04, 7年前 , 10F
11/28 13:04, 10F
推
11/28 14:59, 7年前 , 11F
樓上清楚明白 推
11/28 14:59, 11F
‣ 更多 csuperk 的文章
文章代碼(AID): #1R_NaANJ (Grad-ProbAsk)
‣ 更多 csuperk 的文章
文章代碼(AID): #1R_NaANJ (Grad-ProbAsk)