c - 该算法最坏情况下的时间复杂度是多少？

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

我刚刚学习了 Big-O 概念。所以对于这段代码，据我所知，外部循环运行时间是 n，第二个内部循环运行 n(n+1)/2，内部循环也是 n(n+1)/2。所以运行时间是 O(N^5)？我对吗？

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)。