什么是这三个for循环的复杂性？ [英] What's the complexity of these three for loops?

问题描述

有：

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

• input array A[1...n]
• N length of 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）的。

For loop 2 I would say that the time complexity is O(logN).

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

What's the complexity for loop and 3 (and 2 if I'm wrong) and for the algorithm?

推荐答案

O（N ^ 2）

由于的相互依赖性Ĵ和 K （按 K＆LT;Ĵ），你不能单独考虑循环2和循环3。让 N = 2 ^ M ，为了简化计算。因此，Ĵ将是1，2，4，...，2 ^（M-1），和循环3执行时Ĵ它每次达到次。因此，联合循环2和循环3执行时

Because of the interdependency of j and k (at k<j) you can't consider loop2 and loop3 separately. Let N=2^m, for simplicity of calculation. So, j will be 1, 2, 4, ..., 2^(m-1), and loop3 executes j times each time it is reached. So the combined loop2 and loop3 executes

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

这是一个几何级数和等于 2 ^ M - 1 = N - 1 ，这是O（N）。现在，在循环1掷，O（N），我们得到O（N ^ 2）。

This is a Geometric Progression, and is equal to 2^m - 1 = N - 1, which is O(N). Now throwing in loop1, O(N), and we get O(N^2).

编辑：

下面是perl的code我跑测试这个

Here is the perl code I ran to test this

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 。

Note that we don't hit the expected exactly unless N=2^m.

这篇关于什么是这三个for循环的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！