作者triumphant10 (Look-three-small)
看板C_and_CPP
標題[問題] Big O running time
時間Mon Mar 18 17:10:54 2019
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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1552900261.A.1B8.html
1F：推 OhYiDay: 這是不是台聯大轉學考某年考題啊？！ 03/18 17:19
2F：→ triumphant10: 是喔XD 我不知道耶 03/18 17:23
3F：→ sarafciel: 你走錯版了 C跟C++的程式碼是要宣告明確形態跟分號的 03/18 22:43
4F：推 IhateOGC: N^2 .... 03/18 22:55
5F：推 CoNsTaR: O(n^4) 是怎麼算的... 03/19 08:05
6F：推 CoNsTaR: 你在 prob_solve 也有問，如果是學校要的答案的話會是 O( 03/19 08:07
7F：→ CoNsTaR: n^2) 不是那邊講的 O(1) 03/19 08:07
8F：推 CoNsTaR: 那個版在討論的是問題的複雜度，不是你程式本身的複雜度 03/19 08:09
9F：推 OhYiDay: 這題跟台聯大106計概轉學考14題 一模一樣 如果我沒看錯的 03/19 09:47
10F：→ OhYiDay: 話 可是答案的確是O(N^4）耶 03/19 09:47
11F：→ triumphant10: 抱歉，我發錯版。可以問一下Co大 O(N^2)是如何計算 03/19 14:47
12F：→ triumphant10: 的嗎？ 03/19 14:47
13F：→ loveme00835: 到第 2 層 for 已經是 N^3, N^2 到底怎麼算的? 03/19 15:27
14F：推 CoNsTaR: 抱歉 是我沒有認真看題目 orz 03/19 18:26
15F：→ triumphant10: 沒4沒4 03/19 19:35
16F：推 IhateOGC: 我數學好爛@@ 03/21 09:04