java - 有人可以帮助我告诉我以下算法的复杂性吗？

Question

我试图了解以下解决方案的时间复杂度是 O(n^2) 还是 O(n^3)。

for (int i=1; i<array.length; i++)
     ....
     for (int j=0; j<i; j++)
          ....
          for (int k=i+1; k<array.length-1; k++)
               ...

第一个循环针对索引为 i 的所有数组运行。第二个循环从 0 运行到索引 i。第三个循环从索引 i 运行到数组末尾。

Answer 1

您的代码的复杂性可以通过以下表达式等效评估:

其中n=array.length。

如果您计算这个大和，您会发现结果为 (1/6)*n*(n^2-13) = (1/6)* n^3 - (13/6)*n，复杂度为 O(n^3)。