algorithm - 双for循环的复杂性

Question

我正在尝试使用大 O 表示法计算出 for 循环的复杂性。我以前在其他类(class)中也这样做过，但是这门类(class)比其他类(class)更严格，因为它是基于实际算法的。代码如下:

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++ 是常数时间。

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

Answer 1

第一个例子的外层循环执行了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)。

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

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

等等。