手順

Question

が、私はこの単純なループ上の第一原理からの複雑性分析を実行したいと言う - ここで

for (int i = 0; i < n; i++) 
{ 
    a = i + 1; 
} 

は私がやっていることで、これは正しい手順であるか、私は遠く離れていますか？ I 0の

初期割り当てた：iへの

• 比較N：1つの操作

  ループをn回実行される動作を行うn回

：1回
• インクリメントIを実行N +
• iに+1を代入する：2回の演算をn回実行

したがって、opの総数1 +（n + 1）+ n + 2n = 4n + 2 そして、これはBig Oh（n）の複雑さを持っています。

これは間違いありませんか？それを行う良い方法はありますか？

Answer 1

最終的な結論が正しいアルゴリズムを解析する際、アルゴリズムはしかし、我々は通常以来、行われ、上限と下限だけを探している正確にどのように多くのOPS をカウントO(n)

を避けています正確な詳細は実装依存である可能性があります。

たとえば、loop-unrollingはコード内の比較演算の数を減らすことがあります。計算した演算の正確な数は実際に実行される演算の数ではありません。

また、この前提aはintまたはいくつかのプリミティブ型、及びoperator=、operator+を一定時間で行われているです。 aが、例えばある種の大きな整数や文字列のようなもので、演算子をオーバーロードした場合、はまたはO(n^2)（または他のもの）のアルゴリズムを作るO(|a|)です。 aのタイプです。

Answer 2

これは完全に正しいです。 （ただし、各操作はO（1）時間かかる必要があります。たとえば、操作が関数呼び出しの場合は、実行時の複雑さも考慮する必要があります）

次回は、操作が実行される回数だけをカウントします。たとえば、あなたの例では、実行された各代入操作に対して一定の回数の比較および増分操作が行われることは明らかです。したがって、割り当ての数を数えただけであれば問題ありません。

操作の実行回数を直接カウントすると常に簡単です。たとえば、T（n + 1）= a T（n/b）+ f（n）などの再帰式に到達すると、より困難なケースが発生します。