这三个for循环的复杂度是多少？

Having:

• 输入数组A[1...n]
• N的长度A

算法：

for(int i=N; i>0; i--) { // Loop 1
    for(int j=1; j<N; j=j*2) { // Loop 2
        for(int k=0; k<j; k++) { // Loop 3
            // constant number of operations
        }
    }
}

我知道那个循环1 has O(N)时间复杂度。

For循环2我会说时间复杂度是O(logN).

for 循环的复杂度是多少3 (and 2如果我错了）以及算法？

O(N^2)

由于相互依存j and k (at k<j）你不能单独考虑loop2和loop3。让N=2^m，为了计算简单。所以，j将是 1, 2, 4, ..., 2^(m-1)，loop3 执行j每次达到时。所以loop2和loop3组合起来执行

  1   + 2   + 4   + ... + 2^(m-1)
= 2^0 + 2^1 + 2^2 + ... + 2^(m-1)

这是一个几何级数 http://en.wikipedia.org/wiki/Geometric_progression，并且等于2^m - 1 = N - 1，即 O(N)。现在放入loop1，O(N)，我们得到O(N^2)。

Edit:

这是我运行来测试这个的 perl 代码

print "N\tExpected\tCounted\n";

for my $N (10, 100, 1024, 8192)
{
    my $count = 0;
    for(my $i=$N; $i>0; $i--)
    {
        for(my $j=1; $j<$N; $j*=2)
        {
            for(my $k=0; $k<$j; $k++)
            {
                $count++;
            }
        }
    }
    my $expected_count = $N*$N - $N;
    print "$N\t$expected_count\t$count\n";
}

和输出：

N       Expected        Counted
10      90              150
100     9900            12700
1024    1047552         1047552
8192    67100672        67100672

请注意，我们不会完全达到预期，除非N=2^m.