以下のJavaコードの時間複雑度は

Question

です。これは、合計がtargetNumで割り切れる配列内の別個のトリプレットの総数を見つける簡単なJavaコードです。コードは正常に動作しますが、時間の複雑さがO（n^2）以上でないことを確認する必要があります。

public static void main(String [] args){ 

    int totalNum = 10; 
    int targetNum = 5; 
    int inputArray[] = { 1,10,4,3,2,5,0,1,9,5 }; 


    HashMap<Integer,int[]> tempMap = new HashMap<>(); 
    int tempCount=1; 
    for(int i=0; i<totalNum-2; i++){ 
     for(int j=i+1; j<totalNum; j++){ 

      int num1 = inputArray[i]; 
      int num2 = inputArray[j]; 
      int [] tempArr = new int[2]; 
      tempArr[0] = num1+num2; 
      tempArr[1] = j; 
      tempMap.put(tempCount,tempArr); 
      tempCount++; 
     } 
    } 
    int finalCount=0; 
    for(int i=1; i<tempCount; i++){ 
     int [] tempArr = tempMap.get(i); 
     int val1 = tempArr[0]; 
     int startIndex = tempArr[1]+1; 

     for(int j=startIndex; j<totalNum; j++){ 
      int val2 = inputArray[j]; 
      if((val1+val2)%targetNum == 0){ 
       finalCount++; 
      } 
     } 

    } 
    System.out.print(finalCount); 
} 

Answer 1

投稿されたコードの時間複雑度はO（n^3）です。

最初のループはO（n^2）です。これはネストされたループで、両方のループの範囲はO（n）に比例します。

2番目のループはO（n^3）です。最初のループ（別のループにネストされた1つのループ）とよく似ていますが、外側ループの範囲はO（n^2） O（n）へのループ。それは合計O（n^3）を与える。