配列二重ループ内のペアの時間計算量

Question

私は次のことを知っています: O(n^2),

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

しかし、次のようなことが必要です count = count + 1; 考慮されるのか？複雑な時間方程式を予測または作成する場合、または和表記を使用する場合、

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

重大なタスク「重複をチェックする」で、ティムラフガーデン - アルゴリズムIlluminated_Part 1_ Basics-（2017）42ページに発見することができます。ここでは、ここにあるように、そのように最後のインデックスを取って $ n= $ "Array.length（）"では意味がありません。 j "は国境から実行されます。しかし、これは私たちのカウントに影響を与えません。

常にMAINの場合、カウント操作を選択することです - ここでは「count= count + 1」です。明らかに最善の場合、すなわち最小の操作は、 $ 0 $ です。そして、すなわち最大限の操作量、すなわち最大の演算量は合計である（私はそれを求めてインデックス "i" ） $ t（n）= 1 + 2 + \ cdots +（n-1）=frac {n（n-1）} {2} $ （ケース $ n \ geqlant 2 $ ）

今、 $ \ frac {n（n-1）} {2} \ leqslant \ frac {n \ cdot 2n} {2}= n ^ 2 $ 、それは最終的なケース $ t（n）\ in o（n ^ 2）$ 。

Answer 2

アルゴリズムの時間計算量は、計算モデルによって異なります。アルゴリズムは通常、RAM マシンで分析され、マシンワードの基本操作 (代入、算術、比較など) にコストがかかります。 $O(1)$. 。機械語には長さがある $O(\log n)$, 、 どこ $n$ 入力のサイズです。

あなたの場合、入力のサイズは少なくとも $n$ (長さとして定義されます) array）、 など count 単一の機械語に収まります。アルゴリズムの各基本操作のコスト $O(1)$, したがって、全体的な時間計算量は次のようになります。 $\シータ(n^2)$, アルゴリズムはこれだけ多くの基本的な操作を実行するためです。