为什么此代码的运行时间为O(n ^ 5)? [英] Why is the runtime of this code O(n^5)?

问题描述

已要求我确定此代码的big-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 ⁵ ).谁能解释为什么，或者如何确定呢?是增加最内部循环的工作次数，还是增加每个循环的复杂度?

解决方案

分析此类代码的一种方法是从最内层的循环开始并向外进行工作.那个循环是

    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)的工作，但是第ith次迭代将完成Θ(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 ⁴ ). )，在问题陈述中给出，所以要么

1. 我在这里某处出现数学错误，或者
2. 你的界限不紧.

请记住，big-O表示法用于给出一段代码的运行时上限，因此，如果运行时实际上是Θ( n ⁴ )没错；只是不紧.尽管这不是一个非常有用的界限，也可以说它是O(n ¹⁰⁰ )也不是错误的.

我们可以检查它的一种方法是编写一个程序，该程序只计算最内层循环的运行次数，然后将其与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).换句话说，理论与实践非常接近！

I have been asked to determine the big-O time complexity of this code:

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("*");
                }
            }
        }
    }
}

The answer given is O(n⁵). Can anyone explain why, or how to determine this? Do we add the number of times innermost loop works, or do we multiply the complexities of each loop?

解决方案

One way to analyze code like this is to start from the innermost loop and work outward. That loop is

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

This has time complexity Θ(j). So now let's look at the next loop:

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

This one is interesting. This loop will run Θ(i²) times. Most iterations will do O(1) work, but every ith iteration will do Θ(j) work. We can therefore separate the work done here into two pieces: the baseline Θ(i²) work done just from looping a lot, plus the extra work done from intermittently doing Θ(j) work.

That part where we do Θ(j) work happens every i iterations. This means that work done will be roughly

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

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

= iΘ(i²)

= Θ(i³)

So overall, this loop does Θ(i³) work. This dominates the Θ(i²) work from the outer loop, so the total work done here is Θ(i³).

Finally, we can work our way to the outermost loop, which looks like this:

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

The work done here is roughly

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

= Θ(n⁴)

So overall, the total work done here is Θ(n⁴). This is a tighter bound than the O(n⁵) given in the problem statement, so either

1. I have a math error somewhere in here, or
2. the bound you have isn't tight.

Remember that big-O notation is used to give an upper bound on the runtime of a piece of code, so saying that the runtime is O(n⁵) if the runtime is actually Θ(n⁴) isn't wrong; it's just not tight. It wouldn't be wrong to say it's O(n¹⁰⁰) either, though this isn't a very useful bound.

One way we can check this is to write a program that just counts up how many times the innermost loop runs and to compare that against n⁴ for various values of n. I wrote a program that does just that. It's shown below:

#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;
   }
 }

Here's the output:

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

From this it looks like the runtime is roughly approaching 0.125n⁴, which is roughly n⁴ / 8. That actually makes sense - the hidden constant factor from the innermost loop is 1/2 (since 1 + 2 + 3 + ... + i = i(i+1)/2) and the hidden constant factor from the outermost loop is 1/4 (since 1³ + 2³ + ... + n³ = n²(n + 1)² / 4). In other words, the theory really closely matches the practice!

这篇关于为什么此代码的运行时间为O(n ^ 5)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！