2

入力をサイズ n-1 の 2 つの入力に分割し、それらを再帰的に解く再帰アルゴリズムがあるとします。c と言う一定の時間で結果を結合します。

このための方程式を定式化すると、

T(n) = 2T(n-1) + c

この複雑さを見つけるために、再帰ツリー法を使用しました。入力は各ステップで 2 つに分割されるため、ノードの数は各ステップで 2 乗されますが、1 つの要素のみが削除されるため、すべてのレベルでリストから 1 つの要素のみが失われます。

したがって、この問題の複雑さは Θ(n 2 )であると思います。

私はこの思考過程で正しいですか？そうでない場合、何が間違っていますか?

ありがとうございました。

4

3 に答える 3

5

各ステップのノード数は 2 乗されません。代わりに、すべてのレベルで 2 倍になります。たとえば、ノードの数

  • 問題サイズ n: 1
  • 問題サイズ n - 1:2
  • 問題サイズ n - 2:4
  • 問題サイズ n-3:8
  • 問題サイズ n-4:16
  • ...
  • 問題サイズ n - i: 2 i

その結果、再帰ツリーのノードの総数は 1 + 2 + 4 + 8 + ... + 2 n = 2 n+1 - 1 になります。したがって、実行される作業は c2 n+1 - cになります。 、これは Θ(2 n ) です。これは二次時間ではなく指数時間です。

お役に立てれば！

于 2012-09-06T19:09:39.043 に答える
2

複雑さは実際には指数関数的です: Omega(2^n).

数学的帰納法を使って証明しましょう。簡単にするために-仮定しますc=1

Claim: T(n) >= 2^n
Base: T(0) = 1 (Let's take it as assumption)
Assume the claim is true for each k<n and using it let's prove:
T(n) = 2*T(n-1) + 1 >= 2*2^(n-1) + 1 = 2^n + 1 > 2^n

さて、まとめとして、それがまたあることを示しましょう。これは次のO(2^n)ように結論付けます。Theta(2^n)

Claim: T(n) <= 2*2^n - 1
Base: T(0) = 1 = 2 -1 
Assume the claim is true for each k<n and using it let's prove:
T(n) = 2*T(n-1) + 1 <= 2 * (2*2^(n-1) -1 ) + 1 = 2*2^n -2 + 1 = 2*2^n -1

ご覧2*2^n-1のとおり、@templatetypedef で示されている内容に適合する正確な結果が得られます (上記の証明では、<= は = に簡単に置き換えることができます)。

于 2012-09-06T19:11:53.317 に答える
1

T(n+1)=2T(n)+c から :

T(n+1) + c = 2T(n) + 2c
T(n+1) + c = 2( T(n) + c )
T(n+1) + c = 2^n (T(0) + c)
T(n+1) = 2^n (T(0) + c) - c

これは Θ(2^n) の複雑さをもたらします。

于 2012-09-06T19:13:08.573 に答える