3Sum.javaの漸近的複雑さを見つける方法

Question

ThreeSum.javaの関数countとprintallの時間の複雑さはどうやって得られますか？

public static void printAll(int[] a) { 
    int n = a.length; 
    for (int i = 0; i < n; i++) { 
     for (int j = i+1; j < n; j++) { 
      for (int k = j+1; k < n; k++) { 
       if (a[i] + a[j] + a[k] == 0) { 
        System.out.println(a[i] + " " + a[j] + " " + a[k]); 
       } 
      } 
     } 
    } 
} 


public static int count(int[] a) { 
    int n = a.length; 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     for (int j = i+1; j < n; j++) { 
      for (int k = j+1; k < n; k++) { 
       if (a[i] + a[j] + a[k] == 0) { 
        count++; 
       } 
      } 
     } 
    } 

Answer 1

時間の複雑さの質問は時には非常に厳しいが、これは簡単なケーキです。以下のように、彼らは内側のループのそれぞれは、外側のループ倍のように多くの数を実行する意味のループをネストされているので、あなたは、単に今、

for (int i = 0; i < n; i++) // it runs for n times 
     for (int j = i+1; j < n; j++) // it runs for n-i-1 time 
      for (int k = j+1; k < n; k++) // it runs for n-j-1 times 

それをチェックアウトすることができます。

total = n * (n-i-1) * (n-j-1) 
     = n^3 ... // ignoring all other lower power terms 

したがって、このコードの複雑さはO(n^3)になります。