12

私は最近、再帰と Big-O 記法を含むコンピューター サイエンスの宿題に取り組んでいます。私はこれをかなりよく理解していると思います (ただし、完全ではないことは確かです!)。奇妙なことに、それを見ると、宿題の中で最も単純なもののように見えます。

次の再発の解決策として、big-Oh 表記法を使用して最高の成長率を提供してください。

T(1) = 2

T(n) = 2T(n - 1) + 1 for n>1

選択肢は次のとおりです。

  • O(n log n)
  • O(n^2)
  • O(2^n)
  • O(n^n)

大きな O が上限として機能し、プログラムまたはプロセスにかかる最大の計算量または最大実行時間を表すことを理解しています。この特定の再帰は O(n) であるべきだと思います。なぜなら、再帰は n の値ごとに 1 回しか発生しないからです。n が利用できないので、他の 3 つのオプションである O(nlogn) よりも良いか、悪いかのどちらかです。

だから、私の質問は: なぜこれは O(n) ではないのですか?

4

7 に答える 7

17

再帰を解決するには、置換、再帰ツリー、およびマスター定理という 2 つの異なる方法があります。マスター定理の形式に適合しないため、このケースではマスター定理は機能しません。

他の 2 つの方法を使用することもできますが、この問題を解決する最も簡単な方法は、反復して解決することです。

T(n) = 2T(n-1) + 1
T(n) = 4T(n-2) + 2 + 1
T(n) = 8T(n-3) + 4 + 2 + 1
T(n) = ...

パターンが見えますか？

T(n) = 2 n-1 ⋅T(1) + 2 n-2 + 2 n-3 + ... + 1
T(n) = 2 n-1 ⋅2 + 2 n-2 + 2 n- 3 + ... + 1
T(n) = 2 n + 2 n-2 + 2 n-3 + ... + 1

したがって、最も狭い範囲は Θ(2 n ) です。

于 2008-10-15T20:05:39.140 に答える
15

あなたは質問を少し誤解していると思います。再発を解決するのにかかる時間は尋ねられません。解自体のビッグオー (漸近限界) が何であるかを尋ねています。

あなたがしなければならないことは、閉形式の解、つまり T(n) の非再帰的な式を考え出し、その式の big-O が何であるかを決定することです。

于 2008-10-15T19:37:53.563 に答える
2

これは指数関数的になると思います。n をインクリメントするたびに、値が 2 倍になります。

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T(x) は、次のプログラムの実行時間になります (たとえば)。

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)
于 2008-10-15T19:36:39.353 に答える
2

問題は、再帰の計算コストではなく、再帰の解のビッグオー表記法を求めていることです。

別の言い方をすれば: 再帰は以下を生成します:

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

2、5、11、23、47、...

それを解決する正しい方法は、再帰方程式を解くことです。

于 2008-10-15T19:41:00.687 に答える
1

まず、4つの答えはすべてO（n）よりも悪いです... O（n * log n）は単純な古いO（n）よりも複雑です。大きいもの：8または8 * 3、16または16*4など...

実際の質問に移ります。再帰を行わない場合、一般的な解決策は明らかに一定時間で解決できます

（T（n）= 2 ^（n --1）+ 2 ^（n）-1）、それは彼らが求めているものではありません。

ご覧のとおり、再帰コードを作成すると、次のようになります。

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

明らかにO（n）です。

ですから、それはひどい言い回しの質問のようで、おそらくコードの複雑さではなく、関数自体の成長を求めているのでしょう。それは2^nです。さあ、残りの宿題をしに行きましょう...そしてO（n * log n）について勉強しましょう

于 2008-10-15T22:01:08.080 に答える
1

再帰に対する閉形式の解を計算するのは簡単です。調べてみると、解決策は

T（n）= 3 * 2 ^（n-1）-1

次に、これが確かに解決策であることを帰納法で証明します。規範事例：

T（1）= 3 * 2 ^ 0 --1 = 3 --1=2.わかりました。

誘導：

T（n）= 3 * 2 ^（n-1）-1と仮​​定します。
T（n + 1）= 2 * T（n）+ 1 = 3 * 2 ^ n-2 + 1 = 3 * 2 ^（（n + 1）-1）-1.OK。

ここで、最初の平等は再帰的定義に由来し、2番目は帰納的仮説に由来します。QED。

3 * 2 ^（n-1）-1は明らかにTheta（2 ^ n）であるため、正解は3番目です。

O（n）と答えた人々へ：私はディマにこれ以上同意できませんでした。この問題は、T（n）を計算するためのアルゴリズムの計算の複雑さに対する最も厳しい上限を要求しません（閉じた形式が提供されているため、これはO（1）になります）。問題は、 T（n）自体の最も厳しい上限を要求し、それは指数関数的なものです。

于 2008-10-15T22:29:17.617 に答える
1

これは指数関数的になると思います。n をインクリメントするたびに、計算量が 2 倍になります。

いいえ、そうではありません。それどころか、次のようになります。

n回の反復で実行時間 R が得られるとします。次に、n + 1 回の反復で、正確にR + 1 を取得します。

したがって、成長率は一定であり、全体の実行時間は実際にO ( n ) です。

ただし、彼の解決策は非常に複雑ですが、質問に関するディマの仮定は正しいと思います。

あなたがしなければならないことは、閉形式の解、つまり T(n) の非再帰的な式を考え出し、その式の big-O が何であるかを決定することです。

T ( n ) およびT ( n + 1) の反復の相対的なサイズを調べて、相対的な成長率を判断するだけで十分です。量は明らかに 2 倍になり、漸近的な成長が直接得られます。

于 2008-10-15T19:38:37.183 に答える