java Big O Notation作业——代码片段算法分析？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/216796/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Big O Notation Homework--Code Fragment Algorithm Analysis?
提问by 101010110101
For homework, I was given the following 8 code fragments to analyze and give a Big-Oh notation for the running time. Can anybody please tell me if I'm on the right track?
作为作业，我得到了以下 8 个代码片段来分析并给出运行时间的 Big-Oh 表示法。谁能告诉我我是否在正确的轨道上？
//Fragment 1
for(int i = 0; i < n; i++)
sum++;
I'm thinking O(N) for fragment 1
我在考虑片段 1 的 O(N)
//Fragment 2
for(int i = 0; i < n; i+=2)
sum++;
O(N) for fragment 2 as well
片段 2 也是 O(N)
//Fragment 3
for(int i = 0; i < n; i++)
for( int j = 0; j < n; j++)
sum++;
O(N^2) for fragment 3
片段 3 的 O(N^2)
//Fragment 4
for(int i = 0; i < n; i+=2)
sum++;
for(int j = 0; j < n; j++)
sum++;
O(N) for fragment 4
片段 4 的 O(N)
//Fragment 5
for(int i = 0; i < n; i++)
for( int j = 0; j < n * n; j++)
sum++;
O(N^2) for fragment 5 but the n * n is throwing me off a bit so I'm not quite sure
片段 5 的 O(N^2) 但 n * n 有点让我失望，所以我不太确定
//Fragment 6
for(int i = 0; i < n; i++)
for( int j = 0; j < i; j++)
sum++;
O(N^2) for fragment 6 as well
片段 6 也是 O(N^2)
//Fragment 7
for(int i = 0; i < n; i++)
for( int j = 0; j < n * n; j++)
for(int k = 0; k < j; k++)
sum++;
O(N^3) for fragment 7 but once again the n * n is throwing me off
片段 7 的 O(N^3) 但是 n * n 再次让我失望
//Fragment 8
for(int i = 1; i < n; i = i * 2)
sum++;
O(N) for fragment 8
片段 8 的 O(N)
采纳答案by Kyle Cronin
I think fragment 5 is O(n^3), and similarly fragment 7 is O(n^5)*. It also looks like O(log(n)) for fragment 8.
我认为片段 5 是 O(n^3)，类似地片段 7 是 O(n^5)*。对于片段 8，它看起来也像 O(log(n))。
For the n * n problems, you have to execute the body of the loop n * n times, so it would be O(n^2), then you compound that with the order of the other code. Fragment 8 actually doubles the counter instead of incrementing it, so the larger the problem, the less additional work you have to do, so it's O(log(n))
对于 n * n 问题，您必须执行循环体 n * n 次，因此它将是 O(n^2)，然后您将其与其他代码的顺序复合。Fragment 8 实际上将计数器加倍而不是增加它，所以问题越大，你需要做的额外工作就越少，所以它是 O(log(n))
*edit:Fragment 7 is O(n^5), not O(n^4) as I previously thought. This is because both j and kgo from 1 to n * n. Sorry I didn't catch this earlier.
*编辑：片段 7 是 O(n^5)，而不是我之前认为的 O(n^4)。这是因为 j和 k从 1 到 n * n。抱歉我没有早点发现这个。
回答by Dave L.
Fragment 7 is O(n^5), not O(n^4) as the currently accepted comment claims. Otherwise, it's correct.
片段 7 是 O(n^5)，而不是当前接受的评论声称的 O(n^4)。否则，它是正确的。
回答by Rob Walker
For case 8 try writing out the number of iterations for some values of N and see what the pattern looks like ... it isn't O(N)
对于案例 8，尝试写出某些 N 值的迭代次数，看看模式是什么样的……它不是 O(N)
回答by Arnab Datta
You are on the right track, but here is a tip as to how things might get clearer along the way. Suppose you have some code :
您走在正确的轨道上，但这里有一个提示，说明如何在此过程中变得更加清晰。假设你有一些代码：
for(i = 0; i < n; i++) {
for(j = 0; j < 100; j++){....}
}
Right, consider the fact that you have code at different levels. In this example, you can only see 3 levels so far :
是的，请考虑您拥有不同级别的代码这一事实。在此示例中，您目前只能看到 3 个级别：
- The outer for-loop that goes from 0-n
- Another for-loop that goes from 0-100
- Some code inside, that is marked as
...
- 从 0-n 开始的外部 for 循环
- 另一个从 0 到 100 的 for 循环
- 里面的一些代码，标记为
...
At no point in time should you try to calculate it all in 1 go. This is where most beginners make some kind of arithmetic error. Calculate it individually for each level and then multiply it all together.
您在任何时候都不应该尝试一次性计算所有内容。这是大多数初学者犯某种算术错误的地方。为每个级别单独计算它，然后将其相乘。
Good luck!
祝你好运！
回答by smaclell
You appear to be on the right track. With regards to the N*N what effect do you think it would have? It is another factor of N so it would likely be a higher order.
你似乎走在正确的轨道上。关于 N*N，您认为它会产生什么影响？它是 N 的另一个因数，因此它可能是更高阶的。
Just a warning, I saw another post like this and it was extremely down voted. Be careful. Hereis the post.
只是一个警告，我看到了另一篇这样的帖子，它的投票非常低。当心。这是帖子。
