7

我正在尝试使用 Big O 表示法找出 for 循环的复杂性。我以前在我的其他课程中也这样做过，但是这个比其他的更严格，因为它是在实际算法上的。代码如下：

for(cnt = 0, i=1; i<=n; i++) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

和

for(cnt = 0, i=1; i<=n; i*=2) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

我已经知道第一个循环的复杂度为 O(n)，因为它正在遍历列表 n 次。至于第二个循环，我有点失落。我相信对于每个被测试的 n ，它都会经过 i 次循环。我（错误地）假设这意味着每次评估循环都是 O(n*i) 。我的假设中有什么遗漏的吗？我知道 cnt++ 是常数时间。

感谢您在分析中的帮助。每个循环都在自己的空间中，它们并不在一起。

4

3 回答 3

9

第一个示例的外循环执行n次数。对于外层循环的每次迭代，内层循环都会执行i次数，因此总复杂度可以计算如下：第一次迭代一个，第二次迭代两个，第三次迭代三个，依此类推，再加n上n-第一次迭代。

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2)

第二个例子比较棘手：因为i每次迭代都加倍，所以外层循环只执行了Log2(n)几次。假设它n是 的幂2，则内部循环的总数为

1+2+4+8+16+...+n

这是2^Log2(n)-1 = n-1为了复杂性O(n)。

对于n不是 2 的幂的 s，确切的迭代次数是(2^(Log2(n)+1))-1，它仍然是O(n)：

1      -> 1
2..3   -> 3
4..7   -> 7
8..15  -> 15
16..31 -> 31
32..63 -> 63

等等。

于 2012-09-11T18:39:18.823 回答
0

The first example is O(N^2) and What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop? would be the question that answers that where the key is to note that the inner loop's number of rounds is dependent on n.

The second example is likely O(n log n) since the outer loop is being incremented on a different scale than linear. Look at binary search for an example of a logarithmic complexity case. In the second example, the outer loop is O(log n) and the inner loop is O(n) which combine to give a O(n log n) complexity.

于 2012-09-11T18:40:12.287 回答
0

希望这不是家庭作业，但我确实看到你至少在这里做了一次尝试，所以这是我对此的看法：

cnt递增 n*(n+1)/2 次，这使得两个循环的整个集合为 O(n^2)。第二个循环平均为 O(n/2)，即 O(n)。

于 2012-09-11T18:37:31.503 回答