Question

如何求解递归式？

Answer 1

1、主方法求解递归式

一种求解大部分递归式的公式。给出递归式: T(n) = a * T(n/b) + f(n) ，其中a>=1，b>1，f(n)是给定的函数，T(n)是定义在非负整数上的递归式。

2、递归树求解

用主方法求解不了的递归式，我们可以用递归树来猜测解的上界，然后用代入法来证明解的正确性。递归树的求解精确度取决于画递归树的精确度。

3、代入法

比如我们求解，递归式T(n) = 2T(n/2)+n，我们猜测解是O(nlgn)，我们要寻找到一个常数c，使得T(n)<=cnlgn。

即T(n) <= 2c(n/2)lg(n/2)+n <= cnlgn-cnlg2+n = cnlgn-cn+n

只要c>=1，T(n)<=cnlgn，所以我们的猜测是正确的。

要注意的是，代入法全凭经验，通常用递归树来确定上界，然后用代入法再证明。

扩展资料：

设p0，p1，…，pn，…是一个序列。如果pn和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n0的整数n都是有效的，则称这个关系式为递归关系(recursive relation)式。

如：设(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤i<r)关联起来的方程称做一个递归关系。如关系式:ar=3ar-1 (r≥1)和错排数:Dn=(n-1)(Dn-1+Dn-2) (n=3，4，...)，都是递归关系。