三个for循环的大O表示法

What would be the complexity of the following code? would it be N^2*log(n)?

以下代码的复杂性是什么?它会是N ^ 2 * log(n)吗?

for (int m = 1; m <= n; m++)
{
   for (int k = m; k >= 1; k--)
   {
      for (int i = 1; i <= k; i++)
      {
          //do something here
      }
    }
 }

Any help is appreciated thanks.

任何帮助表示赞赏谢谢。

3 个解决方案

#1

How long does the innermost loop take given the running time of the body of the loop is O(C)? O(C*k)

如果循环体的运行时间是O(C),那么最内层循环需要多长时间? O(C * k)的

How long does the second loop take? O(C*(1+2+3+...+m)) = O(C*m²)

第二个循环需要多长时间? O(C *(1 + 2 + 3 + ... + m))= O(C *m²)

How long does the whole code snipplet take? O(C*(1²+2²+3²+...+n²)) = O(C*n³)

整个代码snipplet需要多长时间? O(C *(1²+2²+3²+ ... +n²))= O(C *n³)

For summing polynomials see Faulhaber's formula.

对于求和多项式,请参阅Faulhaber的公式。

#2

The first loop is executed n times. The second loop executes n/2 times. The third loop is executed k/2 times, which equals to n/4 times.

第一个循环执行n次。第二个循环执行n / 2次。第三个循环执行k / 2次,相当于n / 4次。

This gives you a O(n^3) complexity.

这给你一个O(n ^ 3)的复杂性。

Empirical test:

#include <iostream>

using namespace std;

int main () {
    int n = 1000;

    long first = 0, second = 0, third = 0;

    for (int m = 1; m <= n; m++)
    {
        first++;
       for (int k = m; k >= 1; k--)
       {

          second++;
          for (int i = 1; i <= k; i++)
          {
              third++;
          }
        }
     }

    cout << first << " " << second << " " << third << endl;

    return 0;
}

result:

1000 500500 167167000

#3

If you use Sigma notation, you can come up with the following:

如果您使用Sigma表示法,则可以提出以下内容: