定数に対する機能の再帰？

Question

私はこの漸化与えています：

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

C> 0、> = 1 ...

私の問題は、Tで（a）は、私はあなたができる "再発" どのように理解していないのです定数??再発ツリーを構築しようとしていた場合

のように、私はこれを行うことによって行く：

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

あなたは私が何を意味するか参照してください？ T（a）は何を表していますか？

いずれのリソースも大歓迎です。ありがとう。

OR、繰り返しそれを考える：

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

Answer 1

をあなたが持っている：

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

は、T（N-A）とは何ですか？入力としてn-aを取るだけです。

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

T（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）は、おそらくいくつかの定数です。 希望に役立ちます。

Answer 2

質問よりも遅くなるかもしれませんが、完全性のために、ここに私の答えがあります。