大O的遞歸

Question

我見過很多關於Big-O的問題，但我無法弄清楚這一點。

我練了一些面試問題，我碰到了一個在那裏我發現如果勾股數在整數數組存在。 我覺得有一個簡單的O（n^3）方法來解決它，但我想找到一個更快的方法。

我的問題是，低於澳碼（N^2）或爲O（n^3）？ 我很困惑，因爲即使我只有2個循環，在最壞的情況下，我需要經歷n次n^2，這將是O（n^3）。

public boolean findTriple(int[] array) { 
return findT(0, array); 
} 

public boolean findT(int start, array) { 
if(start == array.length-1) { 
    return false; 
} 
int first = array[start]; 
for(int i = 0; i < array.length; i++) { 
    for(int j = i+1; j < array.length; j++) { 
     if(first*first == array[i]*array[i] + array[j]*array[j] || 
      array[i]*array[i] == array[j]*array[j] + first*first || 
      array[j]*array[j] == first*first + array[i]*array[i]) { 
      return true; 
     } 
    } 
} 
return findT(start+1, array); 
} 

Answer 1

每次調用該函數時都會執行O(n^2)操作。你可以調用你的函數n次。 所以總的複雜性：O(n^3)