包含条件的代码的时间复杂度 [英] Time complexity of the code containing condition

问题描述

foo(int n)
{
   int s=0;
   for(int i=1;i<=n;i++)
     for(int j=1;j<=i*i;j++)
        if(j%i==0)
          for(k=1;k<=j;k++)
            s++;
}

以上代码的时间复杂度是多少？

What is the time complexity of the above code?

我以O（n ^ 5）的形式获取它，但这是不正确的。

I am getting it as O(n^5) but it is not correct.

推荐答案

复杂度为 O（n ^ 4）。

将执行最内层循环每个 i 的i 次。 （ i i 的倍数，<< c $ c> 0..i * i ）

Innermost loop will be executed i times for each i. (i multiples of i within 0..i*i)

就像内循环会运行

j = 0 1 2...i i+1 ...2*i ....3*i .... 4*i .... 5*i... i*i
            x         x       x        x        x      x
    \------/\--------/\-------/                 \------/

这些 x 表示执行最内部的for循环，其复杂度 j 。剩下的时间没有被碰到，只是测试完成了，失败了。

These x denotes the execution of the innermost for loop with complexity j. Rest of the time this is not touched and just the test is done and it fails.

所以现在检查一下，这些 \-- --- / 具有 i * j （j = 1,2,3 ... i）循环和 i 支票。

So now check the thing, these \-----/ has i*j (j = 1,2,3...i) looping and i checks.

现在我们做 i 次。

So total work = i*(1+1+1+...1) + i*(1+2+3+..i)
              = i*i+ i*i*(i+1)/2 ~ i^3

通过外循环，它将为 n ^ 4 。

现在它的含义是什么。整个工作可以这样划分

Now what is the meaning of it. The whole work can be divided in like this

O(i*j+i)
  ^^^ ^
   |   The other cases when it simply skips
  The innermost loop executed

现在，如果我们迭代 j ，那么它的复杂度 O（n ^ 3）。

Now if we iterate over j then it will have complexity O(n^3).

添加了外部循环后，它将为 O（n ^ 4）。

With added external loop it will be O(n^4).

这篇关于包含条件的代码的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！