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