1

私はこの再帰関係を与えられています：

T (n) = T (n − a) + T (a) + cn

C > 0 、a >= 1 ..

私の問題は T (a) にあります。定数を「再帰」する方法がわかりません??

同様に、再帰ツリーを構築しようとしている場合は、次のようにします。

T (n) =>  cn            =>         cn
         /  \                    /    \
      T(a)  T(n - a)           ca      c*(n-a)
                             /    \     /     \
                            ??    ??  T(n-2a)  T(a)

私が何を意味するか分かりますか？T(a) は何を表していますか??

どんなリソースでも大歓迎です。ありがとう。

または、繰り返し考えてみてください。

T (n) = T (n − a) + T (a) + cn
T (n) = T (n -2a) + T (a) + ????
4

2 に答える 2

1

だからあなたは持っています：

T(n) = T(n-a) + T(a) + cn

T（na）とは何ですか？単にnaを入力として使用してください。

T(n-a) = T((n-a)-a) + T(a) + c(n-a)

さて、T（a）とは何ですか？同様に、入力としてaを取ります。

T(a) = T(a-a) + T(a) + ca

それらを組み合わせると、次のようになります。

T(n) = ( T((n-a)-a) + T(a) + c(n-a) )+ ( T(a-a) + T(a) + ca ) + cn
     = T(n-2a) + T(a) + c(n-a) + T(0) + T(a) + ca + cn
     = T(n-2a) + 2T(a) + T(0) + c((n-a) + a + n)

基本ケースにもよりますが、T（0）はおそらく定数です。お役に立てば幸いです。

于 2011-03-25T04:35:55.267 に答える