c++ - 此代码的 Big-O 表示法是什么？

Question

我在决定 N^2 和 NlogN 作为大 O 时遇到问题？让我失望的是来自 k <=j 的第三个嵌套 for 循环。我该如何调和这个？

int Max_Subsequence_Sum( const int A[], const int N )
{
  int This_Sum = 0, Max_Sum = 0;
  for (int i=0; i<N; i++)
  {
    for (int j=i; j<N; j++)
    {
      This_Sum = 0;
      for (int k=i; k<=j; k++)
      {
        This_Sum += A[k];
      }
      if (This_Sum > Max_Sum)
      {
        Max_Sum = This_Sum;
      }
    }
  }
  return Max_Sum;
}

标签： c++algorithmbig-o

Answer 1

这可以通过估计或分析来完成。查看最j-i里面的循环，在第二个循环中有操作。要获得操作总数，总和得到：

(1+N)(2 N + N^2) / 6

制作算法 O(N^3)。估计可以看到有三个循环在某些时候有 O(N) 调用，因此它是 O(N^3)。