为什么这段代码的运行时间是O(n^5)？

Question

有人要求我确定这段代码的大 O 时间复杂度：

function(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < i * i; j++) {
            if (j % i == 0) {
                for (int k = 0; k < j; k++) {
                    printf("*");
                }
            }
        }
    }
}

给出的答案是O(n⁵)。谁能解释为什么，或者如何确定这一点？我们是加上最内层循环的工作次数，还是乘以每个循环的复杂度？

Answer 1

所以 O 时间复杂度是根据感兴趣的任意变量 n 嵌套的每个循环的最大单个迭代计数的乘积。

给你

function (int n) // as in O(n)
{
    for(int i=0;i<n;i++) //  n
    {
    for(int j=i;j<i*i;j++) // n ^ 2
       {

         if(j%i==0) // w/e
           {
             for(int k=0;k<j;k++) // n ^ 2
              {
                printf("*");
              }
            }
       }

     }
}

n * n^2 * n^2 = n^5

有趣的是，您会发现打印的“*”的数量不是 n^5，这是如果 if 条件的结果，您会发现对于给定的正整数 n，* 的计数将是 < n ^ 5 并且可能 > n ^ 4 .

通过使用每个循环的最大迭代次数的乘积，我们可以快速获得函数在 n 任意增加时最终行为的上限。

Answer 2

分析这样的代码的一种方法是从最内层的循环开始，向外工作。该循环是

    for (int k=0; k<j; k++)
    {
      printf("*");
    }

这具有时间复杂度Θ(j)。那么现在让我们看看下一个循环：

for (int j=i; j<i*i; j++)
{
    if (j%i==0)
    {
      // do Theta(j) work
    }
}

这个很有趣。这个循环将运行 Θ(i²) 次。大多数迭代将做 O(1) 的工作，但每 i 次迭代将做 Θ(j) 的工作。因此，我们可以将此处完成的工作分为两部分：基线 Θ(i²) 仅通过大量循环完成的工作，加上间歇性执行 Θ(j) 工作完成的额外工作.

我们做 Θ(j) 工作的那部分每 i 次迭代发生一次。这意味着完成的工作将大致

i + 2i + 3i + 4i + ... + i²

= i(1 + 2 + 3 + 4 + ... + i)

= iΘ(i²)

= Θ(i³)

总的来说，这个循环执行 Θ(i³) 工作。这支配了外循环的 Θ(i²) 工作，所以这里完成的总工作是 Θ(i³).

最后，我们可以找到最外层的循环，如下所示：

for (int i=0; i<n; i++)
{
    // Do Theta(i^3) work
}

这里完成的工作大致是

0³ + 1³ + 2³ + 3³ + ... + (n-1)³

= Θ(n⁴)

总的来说，这里完成的总工作是 Θ(n⁴)。 这是一个比 O(n ⁵) 在问题陈述中给出，所以要么

我这里某处有数学错误，或者
你的界限不紧。

记住大O符号是用来给一段代码的运行时间上界的，所以说运行时间是O(n⁵) 如果运行时间实际上是 Θ(n⁴) 没有错；它只是不紧。说它是 O(n¹⁰⁰) 也没有错，尽管这不是一个非常有用的界限。

我们可以检查这一点的一种方法是编写一个程序，只计算最内层循环运行s 的次数，并将其与 n⁴ 进行比较n 的各种值。我写了一个程序来做到这一点。如下所示：

#include <iostream>
 #include <cstdint>
 #include <cmath>
 using namespace std;
 
 uint64_t countWork(int n) {
   uint64_t result = 0;
 
   for (int i = 0; i < n; i++) {
     for (int j = 1; j < i * i; j++) {
       if (j % i == 0) {
        for (int k = 0; k < j; k++) {
          result++;
        }
      }
    }
   }
 
   return result;
 }

 int main() {
   for (int n = 100; n <= 1000; n += 100) {
     cout << "Ratio of work to n^4 when n = "
          << n << " is " << countWork(n) / pow(double(n), 4.0) 
          << endl;
   }
 }

这是输出：

Ratio of work to n^4 when n = 100 is 0.120871
Ratio of work to n^4 when n = 200 is 0.122926
Ratio of work to n^4 when n = 300 is 0.123615
Ratio of work to n^4 when n = 400 is 0.123961
Ratio of work to n^4 when n = 500 is 0.124168
Ratio of work to n^4 when n = 600 is 0.124307
Ratio of work to n^4 when n = 700 is 0.124406
Ratio of work to n^4 when n = 800 is 0.12448
Ratio of work to n^4 when n = 900 is 0.124537
Ratio of work to n^4 when n = 1000 is 0.124584

由此看来运行时间大致接近0.125n⁴，也就是大致n⁴/ 8. 这实际上是有道理的——最内层循环的隐藏常数因子是 1/2（因为 1 + 2 + 3 + ... + i = i(i+1)/2），最外层循环的隐藏常数因子循环是 1/4（因为 1³ + 2³ + ... + n³ = n²(n+1)² / 4).换句话说，理论真的很贴切！

Answer 3

这道题在最坏情况下的总时间复杂度的数学形式如下：

So complexity is O(n^5).

编辑： 在上面的回答中我没有关注 if 性能。

我们可以按如下方式更改您的代码：

function(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < i * i; j+=i) {
                for (int k = 0; k < j; k++) {
                    printf("*");
                }
        }
    }
}

所以，正如 templatetypedef 提到的，很明显总运行时间是 O(n^4)。

为什么这段代码的运行时间是O(n^5)？

Why is the runtime of this code O(n^5)?

big-o

time-complexity