0

入力サイズに応じて、実行が次のパターンに従う Big-O 表記法でアルゴリズムの計算量を指定するにはどうすればよいですか?

Input size: 4
Number of execution steps: 4 + 3 + 2 + 1 = 10

Input size: 5
Number of execution steps: 5 + 4 + 3 + 2 + 1 = 15

Input size: 6
Number of execution steps: 6 + 5 + 4 + 3 + 2 + 1 = 21
4

3 に答える 3

4

技術的には、複雑さを判断するのに十分な情報が提供されていません。これまでの情報では、5 を超えるすべての入力サイズに対して 21 ステップかかる可能性があります。その場合、サイズ 4 と 5 の動作に関係なく、O(1) になります。複雑さとは、大きな入力サイズの動作を制限することです。 3 つの非常に小さいサイズで何かがどのように動作するかではありません。

サイズ n のステップ数が一般に 1 から n までの数の合計である場合、ステップ数の公式は実際には n(n+1)/2 であり、O(n^2) です。

于 2012-11-30T05:43:17.203 に答える
3

パターン 1 + 2 + 3 + 4 + ....+n に従う系列の場合、系列の合計は n(n+1)/2、つまり O(n^2) として与えられます。

あなたの場合、各レベルで1ステップ少ない（n + n-1 + n-2）ため、ステップ数はn ^ 2になることはありませんが、上限を指定するために大きなOh表記が使用されます関数の成長率したがって、大きな O は O(n^2) になります。これは、ステップ数が n を超えているが、ステップ数が n^2 未満であるためです。

于 2012-11-30T19:34:43.660 に答える
-2

と同じなので、そうあるべきだと思いますO(N): N サイズの配列が与えられ、それを反復します (プラスの計算時間を気にしない場合)。

ちなみに、(n + 1)*n/2アルゴリズムの複雑さではなく、合計の結果だと思います。

于 2012-11-30T05:01:41.437 に答える