4

次のメソッド op は、2 つのプライベート整数値インスタンス変数 n と counter を持つクラスに属します。これらは両方ともコンストラクターで値ゼロに初期化され、その後、メソッド op によってのみ変更されます。

public void op()
{
    if(counter<100)
    {
        op1(); //method with O(1) time complexity
        counter++;
    }else {
        op2(); //method with O(n^2) time complexity
        counter = 0;
    }
    n++;
}

メソッド op1 の時間計算量が O(1) であり、メソッド op2 の時間計算量が O(n^2) であると仮定すると、メソッド op の償却後の時間計算量を最もよく表しているのはどれですか?

A) O(n)

B) O(n log n)

C) O(1)

D) O(n^2)

E) O(n3)

試験の答えは D でした。償却された時間についての私の理解からすると、ほとんどの場合に発生することを数えるので、C であるべきだったと思います。この状況では、最悪のケースは O(n^2) ですが、ほとんどの場合、アルゴリズムは O(1) で実行されます。なぜ O(n^2) なのですか?

4

1 に答える 1

9

償却された実行時間について話すとき、ほとんどの場合に何が起こるかを数えることはできません。まず、ほとんどの場合、どのように定義しますか? 操作の償却実行時間は、操作の平均実行時間と見なすことができます。

今あなたの問題に：

if (counter < 99)簡単にするために、あなたがの代わりに書いたと仮定しますif (counter < 100)。このように、操作は 101 サイクル後ではなく 100 サイクル後に繰り返されます。

以下で を書くときO(...)、私は実際には を意味Θ(...)します。そうでなければ、あなたの質問への答えは些細なことO(1)ですO(n^2)。

op()100 回呼び出した後、合計実行時間は になります99 + 100^2。200 回
呼び出した後、合計実行時間は になります。これらは値によって支配されるため、これらのor については忘れましょう。 したがって、時間を呼び出した後、合計実行時間は次のようになります(簡単にするために、で割り切れると仮定しましょう)。op()2 * 99 + 100^2 + 200^2
992 * 99n^2
op() n100^2 + 200^2 + ... + n^2n100

これが にあることを示しO(n^3)ます。 

Let k = n/100

100^2 + 200^2 + ... + n^2
= 100^2 * (1^2 + 2^2 + ... + k^2)
=(*) O(100^2 * k * k^2)
= O(k^3)
= O(n^3)

(*): sum from 1 to k of i^2 is k (k+1) (2k+1) / 6 = O(k^3)

最後に、 の平均実行時間はop()ですO(n^3 / n) = O(n^2)。したがって、の償却実行時間はop()ですO(n^2)。

于 2012-10-09T20:21:10.963 に答える