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