0

この単純なループの第一原理から複雑さの分析を実行したいとします -

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

これが私がやったことです、これは正しい手順ですか、それとも私は道を外れていますか?

i に 0 の初期割り当て: 1 操作

n 回実行されるループ:

  • i と n の比較: n+1 回実行
  • インクリメント i: n 回実行される操作
  • i +1 を a に代入: 2 つの操作を n 回実行

したがって、操作の総数: 1 + (n+1) + n + 2n = 4n + 2 そして、これには大きな Oh(n) の複雑さがあります。

これは正しいです？それを行うより良い方法はありますか？

4

2 に答える 2

2

最終的な結論は正しいです。アルゴリズムはO(n)

ただし、アルゴリズムを分析する場合、正確な詳細は実装に依存する可能性があるため、通常、実行された操作の数を正確にカウントすることは避け、上限と下限のみを調べます。

たとえば、コードでは、ループ展開によってコード内の比較演算の数が減少する可能性があり、計算した演算の正確な数は、実際に実行された演算の正確な数ではありません。

aまた、これはがintまたは何らかのプリミティブ型でありoperator=、operator+が一定時間で実行されることを前提としています。たとえばa、 がある種の大きな整数または文字列のようなもので、演算子をオーバーロードした場合 -の型の特定の実装に応じて、アルゴリズムoperator=が、 または、 (またはその他のもの) になる可能性があります。O(|a|)O(nlogn)O(n^2)a

于 2012-05-01T12:23:50.310 に答える
1

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

次回は、「重要な」操作を見つけて、その操作が実行された回数だけを数えることができます。たとえば、あなたの例では、実行された割り当て操作ごとに一定の回数の比較操作とインクリメント操作があることは明らかなので、割り当ての数だけを数えれば問題ありません。

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

于 2012-05-01T12:24:08.893 に答える