3

私はJavaの再帰を学んでいますが、次の質問に行き詰まっています。

void f(int n) {
    if (n<=1) return;
    f(n/2);
    System.out.writeln("still continuing...");
    f(n/2);
    f(n/2);
}

これについて 2 つの質問があります。

  1. プログラムが出力する行数を T(n) 、入力を n とすると、T(n) の漸化式はどうなるでしょうか?

  2. マスター定理を使用せずに、質問 1 からの再帰を解くにはどうすればよいですか?

乾杯

4

2 に答える 2

3

T(n) の値の式から始めましょう。私たちは次のことを知っています。

  1. 引数として 0 または 1 を指定して f を呼び出すと、時間がかかります O(1)
  2. より大きな値で f を呼び出すと、f(n / 2) が 3 回呼び出され、一定量の他の作業が行われます。

したがって、次の再帰を得ることができます。

  • T(1) ≤ 1
  • T(n) ≤ 3T(n / 2) + 1

ここでは、「+ O(1)」という用語の代わりに「+ 1」という用語を使用していることに注意してください。これは数学的には不確かですが、いずれにせよ big-O 表記で表される最終結果を探しているので、これはそれほど問題にはなりません。

では、これを解決するにはどうすればよいでしょうか。1 つのオプションは、n に任意の値を差し込んで、何が起こるかを確認することです。(n > 1 と仮定して) から始めます。

T(n) ≤ 3T(n / 2) + 1

ここで、T(n / 2) の呼び出しについて考えてみましょう。n / 2 > 1 の場合、次のようになります。

T(n) ≤ 3T(n / 2) + 1

≤ 3(3T(n / 4) + 1) + 1

= 9T(n / 4) + 3 + 1

それでは、これをゲインに拡張しましょう。

T(n) ≤ 9T(n / 4) + 3 + 1

≤ 9(3T(n / 8) + 3) + 3 + 1

= 27T(n/8) + 9 + 3 + 1

この時点で、パターンが出現していることがわかります。再帰を i 回繰り返した後、完了した作業の合計は次のようになります。

T(n) = 3 i T(n / 2 i ) + sum(i = 0 から i - 1)3 i

このプロセスは、i ≈ lg n のときに発生するn / 2 i ≤ 1 のときに終了します。lg n をプラグインすると、

T(n) ≤ 3 lg n T(1) + sum(i = 0 から i - 1)3 i )

≤ 3 lg n + sum(i = 0 ～ i - 1)3 lg n

さて、 3 lg n = 3 (log3 n / log3 2) = 3 log3 n 1 / log3 2 = n 1 / log3 2なので、この全体は

T(n) ≤ n 1 / log3 2 + sum(i = 0 から (lg n) - 1)3 i

等比級数の和の式を使用すると、この最後の項は (3 lg n - 1) / 2 であり、これは最終的に O(n 1 / log3 2 ) に展開されるため、全体としてこの式は O(n 1 / log 3 2）。

しかし、この式は本当に醜いです。単純化できますか？さて、これがあります：

1 / ログ3 2 = ログ2 3

これにより、実行時間は O(n lg 3 ) で、約 O(n 1.58 ) であることがわかります。

お役に立てれば！

于 2012-02-14T02:38:23.283 に答える
0 
T(n) = 3* T(n/2)+ O(1)

定理が示すように、答えは O(n^(lg 3)) になるはずです。

詳細については、Cormen et al. による Introduction to Algorithm を参照してください。第 4 章を参照してください。再帰方程式の解法は非常に複雑です。しかし、通常、方法は最初に推測し、次に代入を使用して証明します。

于 2012-02-14T04:20:10.247 に答える