[問題] Big O running time

看板C_and_CPP作者 (Look-three-small)時間6年前 (2019/03/18 09:11), 編輯推噓8(8推 0噓 8→)
留言16則, 6人參與, 6年前最新討論串1/1
sum = 0 for (i = 0; i < n; i++){ for (j = 1; j < i*i; j++){ if (j%i == 0){ for (k = 0; k < j; k++){ sum++ } } } } 大家好 我計算出來的 running time 是 O(N^4)，不曉得對不對 以及 如果if條件句是False的話，也必須計算它的次數 那麼正確的寫法應該是甚麼? 因為我只有計算他正確執行時所耗的時間! 麻煩各位了! 謝謝! -- 當年我每回翻開課本，腦袋裡就先告訴自己 這是戰場，我是來拼命的 ! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.106 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1552900261.A.1B8.html
推
03/18 17:19, 6年前 , 1F
這是不是台聯大轉學考某年考題啊？！
03/18 17:19, 1F
→
03/18 17:23, 6年前 , 2F
是喔XD 我不知道耶
03/18 17:23, 2F
→
03/18 22:43, 6年前 , 3F
你走錯版了 C跟C++的程式碼是要宣告明確形態跟分號的
03/18 22:43, 3F
推
03/18 22:55, 6年前 , 4F
N^2 ....
03/18 22:55, 4F
推
03/19 08:05, 6年前 , 5F
O(n^4) 是怎麼算的...
03/19 08:05, 5F
推
03/19 08:07, 6年前 , 6F
你在 prob_solve 也有問，如果是學校要的答案的話會是 O(
03/19 08:07, 6F
→
03/19 08:07, 6年前 , 7F
n^2) 不是那邊講的 O(1)
03/19 08:07, 7F
推
03/19 08:09, 6年前 , 8F
那個版在討論的是問題的複雜度，不是你程式本身的複雜度
03/19 08:09, 8F
推
03/19 09:47, 6年前 , 9F
這題跟台聯大106計概轉學考14題 一模一樣 如果我沒看錯的
03/19 09:47, 9F
→
03/19 09:47, 6年前 , 10F
話 可是答案的確是O(N^4）耶
03/19 09:47, 10F
→
03/19 14:47, 6年前 , 11F
抱歉，我發錯版。可以問一下Co大 O(N^2)是如何計算
03/19 14:47, 11F
→
03/19 14:47, 6年前 , 12F
的嗎？
03/19 14:47, 12F
→
03/19 15:27, 6年前 , 13F
到第 2 層 for 已經是 N^3, N^2 到底怎麼算的?
03/19 15:27, 13F
推
03/19 18:26, 6年前 , 14F
抱歉 是我沒有認真看題目 orz
03/19 18:26, 14F
→
03/19 19:35, 6年前 , 15F
沒4沒4
03/19 19:35, 15F
推
03/21 09:04, 6年前 , 16F
我數學好爛@@
03/21 09:04, 16F
‣ 更多 triumphant10 的文章
文章代碼(AID): #1SZs2b6u (C_and_CPP)