问一道简单的线性非齐次递推式的解法

[hx1997]

T(n)=T(n/2)+T(n/4)+cn, c 为常数. T(1)=1.
是作业题，我太蠢不会解。注意是求非递推解，不是求渐进的界。迭代法不好用，特征方程和主定理用不了。扔进 WolframAlpha 解不出来（
也不用解出来，告诉我解法的关键词就好了…

[ynyounuo]

随手瞎算的：
T(1) = 1

T(2) = T(1) + T(1/2) + cn
= 1 + T(1/2) + cn

T(4) = T(2) + T(1) + cn
= (1 + T(1/2) + cn) + 1 + cn
= 1 + 1 + T(1/2) + 2 * cn

T(8) = T(4) + T(2) + cn
= (1 + 1 + T(1/2) + 2 * cn) + (1 + T(1/2) + cn) + cn
= 1 + 1 + 1 + 2T(1/2) + 3 * cn

T(n) = log_2(n) + (log_2(n) - 1) * T(1/2) + c * log_2(n) * n


Mathematica 的结果：

[hx1997]

@ynyounuo 完了，跟我算的完全不一样… 你的是 O(nlogn)，Mathematica 的结果是 O(n^2)，我的是 O(n)……

[hx1997]

@ynyounuo 怀疑题目出错了，哪里会这么难…

[hx1997]

@hx1997 咦好像又不是 O(n^2)，当我没说

[ynyounuo]

@hx1997
一楼明显有问题，可以忽略。
Mathematica 算带对数的运算就很鸡肋，也没啥参考性。
如果我想的没错的话，这题应该无解，除非给出另外一个 T(c) = d。

[hx1997]

@ynyounuo 嗯，我觉得应该是让我们给出个界比较合理，谢谢啦

[Xs0ul]

@hx1997 #6 试试变量代换，s = log_2(n), n = 2 ^ s

递推式等价的应该变成 T(2^s) = T(2^(s-1)) + T(2^(s-2)) + c * 2 ^ s

定义 R(s) = T(2^s), 改写为 R(s) = R(s-1) + R(s-2) + c * 2 ^ s

齐次部分是斐波那契数列， 最后的 c * 2 ^ s，凑了下是 G(s) = c * 2 ^ (s+2)

所以 R(s) = F(s) + G(s)，其中 F 是斐波那契的解

最后得到 T(n) = R(log_2(n)) = F(log_2(n)) + G(log_2(n))

以上完全是按照函数来做的，因为原来定义里有 1/2，已经不算是数列了

[hx1997]

@Xs0ul 真的解出来了，谢谢大佬！🙏

[hx1997]

@Xs0ul 看了这方法，只能感叹一句太精妙了… 之前用递归树算的 O(n)，也没办法给出具体表达式。