为什么这段代码的运行时间为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

分析这样的代码的一种方法是从最里面的循环开始并向外工作.那个循环是

    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)工作,但每次迭代都将执行Θ(j)工作.因此,我们可以将这里完成的工作分为两部分:基线Θ(i ²)工作仅仅是从循环中完成的,加上间歇性地进行Θ(j)工作所做的额外工作.

我们做Θ(j)工作的那一部分每次迭代都会发生.这意味着完成的工作将是粗略的

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 ⁵)更严格,所以也是如此

1. 我在这里的某个地方有数学错误,或者
2. 你所拥有的约束并不紧张.

请记住,big-O表示法用于给出一段代码的运行时的上限,因此如果运行时实际上是Θ(n ⁴)并没有错,那么说运行时为O(n ⁵); 它只是不紧张.说它是O(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 ).换句话说,理论真的与实践密切相关!