java - これら 2 つの for ループの複雑さはどのくらいですか?

Question

このアルゴリズムの時間計算量は? 私の最初の推測では、それはO(log[n])ですか?

int array[] = new int[100];
int counter = 0;

for ( int i = 0; i < array.length; i++ ) {
    for ( int j = i + 1; j < array.length; j++ ) {
        if ( array[i] == array[j] ) {
            counter++;
        }
    }
}

Answer 1

アルゴリズムの時間の複雑さを推測する正式な方法:

Answer 2

考えられる答えは 2 つあります。技術的に正しいのは ですO(1)。これは、配列の長さが一定であるため、内側のループの反復回数が一定であるためです。

代わりに、配列の長さが n であると仮定すると、内側のループの反復回数は n-1、n-2、n-3、...、1、0 になります。長さ n の算術級数の合計は 0 から始まりO(n^2)ます。

Answer 3

The order is O(n^2).

説明: 配列の長さが n であるとします。
次に、最初のループの反復:
2 番目のループの n-2 反復があります。
したがって、合計時間は次のようになります: (n-2)+(n-2)+............(n-2) //n-1 回の
場合: (n-1 )*(n-2)。