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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2431 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

解法

递推解

迭代法

定理

9 条回复 • 2018-03-28 01:43:37 +08:00

ynyounuo

2018-03-27 15:37:32 +08:00

随手瞎算的：
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

2018-03-27 17:47:58 +08:00 via Android

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

hx1997

2018-03-27 17:49:23 +08:00 via Android

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

hx1997

2018-03-27 17:52:12 +08:00 via Android

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

ynyounuo

2018-03-27 19:50:57 +08:00 via iPhone

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

hx1997

2018-03-27 21:50:49 +08:00 via Android

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

Xs0ul

2018-03-27 22:25:03 +08:00

@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

2018-03-28 01:36:26 +08:00 via Android

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

hx1997

2018-03-28 01:43:37 +08:00 via Android

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