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

Question

有:

• 输入数组 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有O(N)时间复杂性.

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

循环和3(2如果我错了)和算法的复杂性是什么？

Answer 1

O(N ^ 2)

由于j和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)

这是几何级数,等于2^m - 1 = N - 1,即O(N).现在抛出loop1,O(N),我们得到O(N ^ 2).

编辑:

这是我运行的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.