時間の複雑さ（試験のために勉強する）

Question

私は現在アルゴリズムの試験に勉強中ですが、私は時間の複雑さについてJavaの質問を解決しようとしていますが、実際にそれを行う方法を理解することはできません。私は予想される時間の複雑さを計算すると仮定しています。 Nは正の整数です。

for (int i=0; i < N; i++) 
    for (int j=i+1; j < N; i++) { 
    int x=j+1; int h=N-1; int k; 
     while(x<h) { 
     k=(x+h)/2; 
      if (a[i]+a[j]+a[k] == 0) { cnt++; break;} 
      if (a[i]+a[j]+a[k] < 0) x=k+1; 
      else h=k-1; 
}} 

最初のforループはN回実行し、2回目はN-1を実行する必要があります。 xはj + 1なので、x = N-2と推測されます。私はwhileループでそれを考えたり、何か正しいことをしたかどうかを知りません。本当に助けに感謝しますか？

Answer 1

時間複雑度関数を部分的に作成します。

要約T（N）中のSO

for (int i=0; i < N; i++) //Takes linear O(n) 
    for (int j=i+1; j < N; i++) { //Takes linear O(n) and in computer science we can safely assume -1 is irrelevant at N-1 in big O notation 
    int x=j+1; int h=N-1; int k; // 3 x O(1) 
    while(x < h) { // Worst case is when j equals i + 1 where i = 0 so x is at lowest 2 and h equals to N-1 so h depends on N. So again loop takes linear O(n) time. 
     k=(x+h)/2; // Takes O(1) time 
     if (a[i]+a[j]+a[k] == 0) { // Takes O(1) time and if this gives true we do break from the while loop 
     cnt++; // Takes O(1) time 
     break; // Takes O(1) time 
     } 
     if (a[i]+a[j]+a[k] < 0) { // Takes O(1) time 
     x=k+1; // Takes O(1) time 
     } else { 
     h=k-1; // Takes O(1) time 
     } 
    } 
    } 
} 

O（N^3）及びΩ（N^2） より具体的T（N）= N * N-1 * N-2 + 10とこれに等しいです最後に、avarageのループはO（N/2）時間かかりますが、コンピュータサイエンスではO（N）と同じです。

私たちは最悪の場合と最良の場合にのみ興味があります。さらに大きなO記法実際 T（N）を混同し

= O（G（N））は、この意味：

を私はこの答えは少しでも役に立てば幸い...