次の配列ダブルルックアップのBig O表記における時間複雑度の計算方法

Question

次のアルゴリズムの時間複雑度はどのくらいでしょうか？助けてもらえますか

public class Util 
{ 

    public static int GetDistance(int[] array) 
    { 
     //Find the max seperation of two same numbers inside an array for example 
     // {1,2,4,1,5,9,0,4,15,1,2} should return 9 (position of '1' at 9th and 0th location) 

     int N = array.Length; 
     int maxDistance=0; 
     for (int i = 0; i < N; i++) 
     { 
      for (int j = (N-1); j > i; j--) 
      { 
       if (array[j]==array[i]) 
        if(maxDistance < (j-i)) 
         maxDistance = j- i; 
      }//End of inner for 

     }//End of for 
     System.Console.WriteLine("maxDistance " + maxDistance); 
     return maxDistance ; 
    } //End of Function 

} //End of Class 

Answer 1

内部ループ（一定時間内の操作）を見ます。内部ループは正確にN-1-i回実行されます。

次に、外部ループは、正確にN回実行され、値が増加すると、iとなります。総作業負荷には、体内の実行が含まれます。

(N-1) + (N-2) + (N-3) + ... + 1 

この合計は三角数であり、それが

(N-1).N/2 

これは、O（N²）であると等しいことを示すために、大したことではありません。

Answer 2

あなたはN回反復する2つのforループを持っています（2つ目はNという意味になりますが、Nは大きく、反復回数は大きくなります）。ループ内で、操作はO

をである（1） だから、完全にあなたはO（1）* O（N^2）= O（N^2）