这个算法的最坏时间复杂度是什么？

Question

void intFunction (int n, int value)
{
     int b,c;
     for (int j = 4; j < n; j++) {
          for (int i = 0; i < j; i++) {
               b *= val;
               for (int k = 0; k < n; ++k)
                    c += b;
          }
     }
}

我刚学习了大O符号。所以对于这段代码，从我的理解来看，外部循环运行时间为n，第二个内部循环运行n(n+1)/2次，而内部的循环也是n(n+1)/2次。因此，运行时间将会是O(N^5)？我的理解正确吗？

- user3923936

---

不，你错了。最外层循环是O(n)，内层循环也是O(n)，最里层循环也是O(n)。总体来看，时间复杂度是O(n^3)。 - perreal

这个问题似乎不适合讨论，因为它涉及到渐近分析。 - tmyklebu

@Juan，j 从4开始，但会增加到 n - 1。 - perreal

@tmyklebu：不是SO的离题话题 - Michael Foukarakis

@MichaelFoukarakis：当然是的。这与编程无关；如果有什么问题，CS StackExchange就是正确的地方。 （除此之外，这个问题几乎肯定已经被重复提问很多次了。） - tmyklebu

Answer 1

外层循环：

for (int j = 4; j < n; j++) 

该循环迭代 n - 4 次，因此它是 O(n)。内部循环：

for (int i = 0; i < j; i++)

最多迭代n - 5次，因此这也是O(n)。内部最深层的迭代：

for (int k = 0; k < n; ++k)

迭代 n 次，因此时间复杂度为 O(n)。最终的复杂度为 O(n * n * n) = O(n^3)。

- perreal

Answer 2

解决以下公式将给出您确切的迭代次数（并推导增长复杂度的顺序）：

结果经过实证验证！

- Mohamed Ennahdi El Idrissi

---

我明白了。那中间的循环呢？它不是求和吗？ - user3923936

我看到了三个循环，因为我看到了三个求和。我不确定你的问题是关于什么的。 - Mohamed Ennahdi El Idrissi

Answer 3

让我们通过迭代次数来验证时间复杂度！

第一个循环 --->

for (int j = 4; j < n; j++){...}  // it will iterate for n-4 times.

第二个循环--->

for (int i = 0; i < j; i++){...}  //it'll iterate for j-1 times for each iteration of outer loop started by j. See,this is dependent on First Loop(the outermost loop)...

第三个循环 --->

for (int k = 0; k < n; ++k){...}  //it'll always run n times independent to any previous-iteration whenever it is executed

因此，案例的总迭代过程将是（在简化版本中）：-

(n-4)*(j-1)*n times. 

但是，j本身的取值范围从4到n-1不等。因此，j在一定程度上取决于n，即4<=j<=n-1。// 因此，在这里，j将迭代n-5次...

具体处理方式如下：

n*n-5*n=n^3-5*n^2.

它等于O(n^3)。

因此，在最坏情况分析中，迭代次数将为n^3-5*n^2，时间复杂度为O(n^3)。

- Am_I_Helpful