再帰の大きなO

Question

私はBig-Oの多くの質問を見たことがありますが、私はこれを理解できませんでした。

私はいくつかの面接の質問を練習していました。ピタゴラスのトリプレットが整数配列に存在するかどうかを調べる必要があります。 私はそれを解決するには簡単なO（n^3）方法があるとわかりましたが、より速い方法を見つけたいと思っていました。

私の質問は、O（n^2）またはO（n^3）以下のコードですか？ 私は2つのループしか持っていないにもかかわらず、最悪の場合、n^2のn回を通過する必要があります。これは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)