9

自分自身を 1 回だけ呼び出すアルゴリズムの再帰関係を行う方法は知っていますが、1 回の発生で自分自身を複数回呼び出す方法はわかりません。

例えば：

T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
4

5 に答える 5

7

再帰ツリーを使用します。CLRS「IntrotoAlgorithm」の再帰ツリーの最後の例を参照してください。

T（n）= T（n / 2）+ T（n / 4）+ T（n / 8）+n。ルートはn（コスト）であり、3つの再帰に分割されます。したがって、再帰ツリーは次のようになります。

T（n）= n = n T（n / 2）T（n / 4）T（n / 8）（n / 2）（n / 4）（n / 8）T（n / 4）T（n / 8）T（n / 16）T（n / 8）T（n / 16）T（n / 32）T（n / 16）T（n / 32）T（n / 64）

                                             n---------------------------------> n      

                             (n/2)         (n/4)           (n/8)--------------> (7/8)n

                         n/4 n/8 n/16  n/8 n/16 n/32  n/16 n/32 n/64)--------> (49/64)n
                                            ...

最長パス：左端の分岐= n-> n / 2-> n / 4-> ...-> 1

最短ブランチ：右端のブランチ= n-> n / 8-> n-> 64-> ...-> 1

葉の数（l）：3 ^ log_8（n）<l <3 ^ log_2（n）=> n ^ 0.5 <l <n ^ 1.585

ツリーを見てください-log_8（n）レベルまではツリーがいっぱいになり、下に行くにつれて、ますます多くの内部ノードがなくなります。この理論によって、私たちは限界を与えることができます、

T（n）= Big-Oh（Summation j = 0 to log_2（n）-1（7/8）^ jn）= ... => T（n）= O（n）。T（n）= Big-Omega（Summation j = 0 to log_8（n）-1（7/8）^ jn）= ... => T（n）= Big-Omega（n）。

したがって、T（n）= Theta（n）です。

ここでのポイントは次のとおりです。T（n / 2）パスの長さが最も長くなります。

これは完全な三分木であってはなりません...高さ=nの対数基数2＆葉の数はn未満でなければなりません...

うまくいけば、おそらくこの方法であなたは問題を解決することができます。

于 2011-08-31T17:24:28.613 に答える
3

これを解決するには2つの方法があります。1 つは、再帰を展開して類似点を見つけることです。これには創意工夫が必要であり、非常に困難な場合があります。別の方法は、Akra-Bazzi メソッドを使用することです。

この場合、、、、、。g(x) = n_ a1 = a2 = a3 = 1_ 方程式を解くb1 = 1/2b2 = 1/4b3 = 1/8

ここに画像の説明を入力

あなたはどちら1/2^p + 1/4^p + 1/8^p = 1を手に入れますかp = 0.87915。積分を解くと が得られますここに画像の説明を入力。つまり、複雑さは次のとおりです。O(n)

于 2015-12-13T10:41:29.957 に答える
0

例としてフィボナッチ数列 (難しい方法) をコーディングするのと同じように、次の行に沿って何かを入力するだけです。

long fib(long n){
 if(n <= 1) return n; 
 else return fib(n-1) + fib(n-2);
}

または、さらに良いことに、グローバル変数を使用してメモ化し、はるかに高速にします。もう一度、フィボナッチ数列で:

static ArrayList<Long>fib_global = new ArrayList(1000); 
  //delcare a global variable that can be appended to
long fib(long n){
   if(n >= fib_global.length)fib_global.add(fib(n-1) + fib(n-2));
   return fib_global.get(n);
}

コードは一度に 1 つの呼び出しのみを実行し、ほとんどの場合、入力した左から右の順序で実行されるため、実行に必要な回数を気にする必要はありません。何かを呼び出します。

于 2011-04-11T22:35:32.017 に答える