algorithm - 功能性复发是恒定的？

Question

我得到了这个递归关系：

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) + ????

Answer 1

可能比提出问题要晚得多，但为了完整起见，这是我对答案的看法。

Answer 2

所以你有了：

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) 可能是一些常数。希望有帮助。