この関数の時間複雑度はO（1）ですか？

Question

今日のアルゴリズムに関する古いノートをレビューしていましたが、これが私の考えです。

複雑度O(1)は、関数の実行時間がデータとは独立していることを意味します。

配列のすべての要素を追加する関数があるとしましょう。

int add(int[] array){ 
    int sum =0; 
    for (int i=0;i<ARRAY_MAX_SIZE;i++){ 
     sum= sum + (i<array.length?array[i]:0); 
    } 
    return sum; 
} 

ここで、ARRAY_MAX_SIZEは可能な最大サイズの配列です。私はこのコードが効率的ではないことを知っています。私はこれについて議論したくありません。しかし、演算子+は毎回同じ量の時間と呼ばれ、データのサイズの影響を受けません。

これは、この関数の複雑さがO（1）であることを意味しますか？

Answer 1

はい。 O（1）は、一定時間を意味し、高速/効率/最適ではありません。

Big-Oの複雑さは、一定のステップの複雑さを無視します。除算（遅い）は、インクリメント（高速）と同様に「複雑」です。

Answer 2

配列のサイズが最大であれば、複雑さはO(1)になります。しかしこれには別の結果があります。 array.lengthがARRAY_MAX_SIZE,未満であることが必要となるので、array.lengthも同様に、次のO(1)を作り、定数によって制限さ：

for(int i=0; i<array.length; i++) { 
    sum = sum + array[i]; 
} 

だから我々は、通常は、アルゴリズムの複雑さのために有用な結果を得るために、配列サイズ上の任意の制限を無視すると思います。

これは明らかにARRAY_MAX_SIZEが配列の最大可能サイズ（質問で定義されている）であり、他の値ではないと仮定しています。

Answer 3

実際の回答は「それに依存する」です。ここで起こって物事の異なる2組あります

：

• ARRAY_MAX_SIZE回、あなた：
  • インクリメントとは
  • が総
• array.lengthに追加するループをテスト回、あなた：;
  • アクセスarray[i]
• ARRAY_MAX_SIZE - array.length回、あなた:;
  • 負荷定数ゼロ

だから、合計ランタイムは

t = k_1 * ARRAY_MAX_SIZE + 
    k_2 * n + 
    k_3 * (ARRAY_MAX_SIZE - n) 

だから、あなたはどのようk_2を見て、k_3比較です。彼らは基本的に等しいのですか？その後、それはO(1)です。 k_2 >> k_3ですか？その後、それはO(n)です。

なぜでしょうかk_2 >> k_3？ array[i]はメモリアクセス、およびmemory is comparatively very slowですので：唯一興味深い部分がある

Answer 4

array[i]のみn回使用されています。つまり、i番目の要素がn回になるように配列を参照する操作を追加します。私はこれを通常は数えませんが、これはおそらくO(n)になりませんか？ちょうど悪魔の主張を果たしている。

私はこれが本当にO(1)に相当すると思います。

int add(int[] array){ 
    int sum =0; 
    int len = array.length; 
    for (int i=0;i<ARRAY_MAX_SIZE;i++){ 
     sum= sum + array[i%len] & (i < len ? 0xFFFFFFFF : 0); 
    } 
    return sum; 
}