当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - What's the Big-Oh for nested loops i=0..n-2, j=i+1..n-1?

问题描述:

Given the following code:

for (int i = 0; i < n-1; ++i)

{

for (int j = i+1; j < n; ++j)

{

// Do work.

}

}

What is the Big-Oh value for it (over n)? I'm thinking it's O(N^2) but I'm not sure.

I did find a similar question here: complexity for nested loops

but it's not quite the same I think.

网友答案:

Yes, that's O(N^2). Pair up the iterations of the inner loop in the beginning and at the end of the outer loop, like this:

The inner loop will execute...

  • N-1 times on the first iteration of the outer loop, and 1 time on the last iteration
  • N-2 times on the second iteration of the outer loop, and 2 times on the second to last iteration
  • N-3 times on the third iteration of the outer loop, and 3 times on the third to last iteration
  • ... and so on; you will have N/2 pairs like that; when N is odd, the last pair is incomplete.

You can see that each of the pairs executes a total of N times, and you have N/2 such pairs, for a total of N*(N-1)/2 times.

The way the formula is derived comes from the derivation of the formula for the sum of arithmetic progression with the common difference of 1.

网友答案:

It should be possible to check it this way.

int z = 0, n = 10; // try 20 etc
for (int i = 0; i < n-1; ++i)
{
    for (int j = i+1; j < n; ++j)
    {
        z++;
    }
}

Now, check the value of z.

With n = 10; z becomes 45
With n = 20; z becomes 190
With n = 40; z becomes 780

A doubling in n caused z to become ~4 times its value. Hence, it is approximately O(n^2).

网友答案:

Methodically, using Sigma notation (empirically verified), you can obtain the exact number of iterations plus the order of growth complexity:

分享给朋友:
您可能感兴趣的文章:
随机阅读: