有人能幫助我告訴我下面的算法的複雜性嗎？

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

你的代碼的複雜性可以從以下表達式equivalenty評價：

其中n=array.length。

如果你計算這個之大，你會發現它會導致對(1/6)*n*(n^2-13) = (1/6)*n^3 - (13/6)*n，這給的O(n^3)複雜性。