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

所以你有:

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)？同样，将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) 可能是某个常数。希望对您有所帮助。