1

C++ で Robert Sedwick の書籍を使用してアルゴリズムを自力で読む

サイズ N の問題を 2 つの独立した (空でない) 部分に分割する再帰関数は、再帰的にそれ自体を N 回未満呼び出します。

パーツがサイズ k とサイズ Nk の 1 つである場合、使用する再帰呼び出しの総数は T(n) = T(k) + T(nk) + 1 で、N>=1 で T( 1) = 0。

解 T(N) = N-1 は帰納法により即時です。サイズの合計が N 未満の値になる場合、呼び出しの数が N-1 未満であるという証明は、同じ帰納的な議論から得られます。

上記のテキストに関する私の質問は

  1. 筆者はどのようにして帰納法によって T(N) = N-1 の解を導き出したのでしょうか? 理解するのを手伝ってください。
  2. 著者は、「サイズの合計が N 未満の値になる場合、呼び出し回数が N-1 未満であるという証明は、同じ帰納的議論から導かれる」とはどういう意味ですか?

私は数学的帰納法に慣れていないので、理解するのが難しいです。

お時間をいただきありがとうございます。

4

3 に答える 3

0

あなたの質問の最初の部分について、あなたがこの漸化式を持っているので、最初に私の意見では著者が間違っていることに言及する必要があります：

T（n）= T（k）+ T（nk）+ 2：n> 1の場合、1つではなく2つの小さなパーツを呼び出したためです。ここで、2（n-1）再帰呼び出しを想定しています。

それでは、誘導で確認してみましょう。

T(1) -> no recursive call.
T(2) = T(1) + T(1) + 2 : two recursive call.
...
T(n) = T(k) + T(n-k) + 2 = 2(k-1) + 2(n-k-1) + 2 = 2n-2 = 2(n-1).

また、質問の2番目の部分について、作成者とは、サイズkの部分とサイズn-2kの別の部分の合計がk> 1の場合のように、部分の合計がnより小さくなるように2つの部分に分割することを意味します。

于 2012-09-04T14:02:18.960 に答える
0

まず第一に、私たちは「帰納法による解決策を持ってきた」のではなく、最初の推測を証明するために帰納法を使用します。さて、推測するために、再帰ツリーのような方法を使用できます。あなたの問題では、最も多くの再帰が発生する
ため、最悪のケースは です。k=1また、各レベルでのコストもわかっています。

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

次に、 のコストを見つけて、T(n-1)それを cost に追加する必要がありますT(n)=1。
最終結果は だと思いN-1ます。このステップでは、推測を証明するために帰納法を使用します。

更新:
T(n) のコストは 1 ( T(1) はゼロ、計算される T(n-1) に加えて 1 => 1 )、T(n-1) のコストも 1 です (同じロジック）。n-1の深さで下ります。最後の 1 つは T(1) で、これはゼロです。（木を描いてください、それはあなたが理解するのを助けるでしょう）。再帰木
と呼ばれる成長の順序を推測するこの方法。これで、帰納法で証明できます。

帰納法を適用して仮説を証明する方法の詳細については、CLRSなどのテキスト ブックを参照してください。

于 2012-09-04T14:15:21.993 に答える