2

このコードの漸近的な複雑さを教えてください。

f(n):
if (n<=2) then return 1;
else { 
     if (n>950) then { i=n/2; return f(i);}
     else return f(n-2);
}

私は2つの解決策を考えました。

a)

O(1)         when n<=2
T(n/2) + 1   when n > 950
T(n-2) + 1   when 950>=n>2

そして再発を解決します：

O(1)         when n<=2
Θ(log n)     when n > 950
O(n^2)       when 950>=n>2

b) ただし、n が 950 より大きい場合、アルゴリズムは i が 950 より小さくなるまで f(i) を呼び出し、その後 f(n-2) の呼び出しを続行するため、最後の 2 つのステートメントの複雑さについてはよくわかりません。したがって、他の解決策は次のとおりです。

O(1)                  when n<=2
T(n/2) + T(n-2) + 1   otherwise

そして再発を解決します：

O(1)         when n<=2
O(n^2)       otherwise

実際には2番目が正しいと思いますが、よくわかりません。ご協力いただきありがとうございます。

4

3 に答える 3

2

さて、nが本当に大きい場合に何が起こるかを考えることから始めましょう。最終的に、nは十分に大きくなり、他のすべてを支配します。そして確かに、n = 950に達するまで、O（lg n）が得られます。ここで、「lg」は対数の基数2を示します（なぜこれをすぐに知っているのですか？nのサイズが累乗で減少するため）反復ごとに2つ。）

nが950に下がると、毎回2ずつ減少します。したがって、950から2はO（n）になります。これは、基本的に値の半分に達し、その1/2が定数に消えるためです。

ただし、lgn>950/2のnの値が存在することに注意してください。エルゴのlgn項は、nの値を支配します。O（lg n）。

于 2012-07-02T10:12:43.310 に答える
2

n<=2 の場合は O(1)。

O(1) for 2 < n <= 950 - 一定の時間がかかります (950/2)。

n>950 の場合は T(n/2)。

T(n) = T(n/2) + 0(1) となります。

複雑さの合計 = O(log n)。

于 2012-07-02T18:08:42.360 に答える
0

漸近的な動作は、複雑さの成長の説明であり、 nの個々の値を差し込むことができる関数ではありません。したがって、 nの異なる値に対して 2 つまたは 3 つの異なるステートメントを使用しても意味がありません。

n -> 無限大であるため、n < 950 の動作は無視できるものになると考えてください。

于 2012-07-02T10:08:46.627 に答える