java - 大O符号作业--代码片段算法分析？

Question

作为家庭作业，我得到了以下 8 个代码片段来分析并给出运行时间的 Big-Oh 符号。谁能告诉我我是否走在正确的轨道上？

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

我在考虑片段 1 的 O(N)

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

片段 2 也是 O(N)

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

片段 3 的 O(N^2)

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

片段 4 的 O(N)

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

片段 5 的 O(N^2) 但 n * n 让我有点失望，所以我不太确定

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

片段 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++;

片段 7 的 O(N^3) 但再次 n * n 让我失望

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

片段 8 的 O(N)

score 20 · Accepted Answer

我认为片段 5 是 O(n^3)，类似地片段 7 是 O(n^5)*。对于片段 8，它看起来也像 O(log(n))。

对于 n * n 个问题，你必须执行循环体 n * n 次，所以它是 O(n^2)，然后你将它与其他代码的顺序复合。Fragment 8 实际上将计数器加倍而不是增加它，所以问题越大，你要做的额外工作就越少，所以它是 O(log(n))

*编辑：片段 7 是 O(n^5)，而不是我之前认为的 O(n^4)。这是因为 j和 k都从 1 变为 n * n。抱歉我没有早点发现这个。

score 7 · Accepted Answer

7

片段 7 是 O(n^5)，而不是当前接受的评论声称的 O(n^4)。否则，它是正确的。

于 2008-10-20T18:18:09.307 回答

score 2 · Accepted Answer

对于案例 8，尝试写出 N 的某些值的迭代次数，看看模式是什么样的......它不是 O(N)

score 0 · Accepted Answer

你似乎走在正确的轨道上。关于 N*N，您认为它会产生什么影响？它是 N 的另一个因素，因此它可能是更高的阶数。

只是一个警告，我看到另一篇这样的帖子，它被极低的投票。当心。这是帖子。

score 0 · Accepted Answer

你走在正确的轨道上，但这里有一个关于如何让事情变得更清晰的提示。假设你有一些代码：

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

对，考虑一下你有不同级别的代码这一事实。在此示例中，到目前为止您只能看到 3 个级别：

在任何时候，您都不应该尝试一次性计算所有内容。这是大多数初学者犯某种算术错误的地方。为每个级别单独计算它，然后将它们相乘。

祝你好运！

5 回答 5