求解递归式的基本方法

递归式

一个递归式就是一个等式或不等式，
它通过更小的输入上的函数值来描述一个函数。
例如:

一、代入法

1. 猜测解的形式。

2. 用数学归纳法求出解中的常数，并证明解是正确的。

例子

一般解法

求解: T(n) = T(n-1) + n

假设其解为O(n^2)，即 T(n) = O(n^2)
代入法要求: 证明选择常数 c>0 ，可得 T(n) ≤ c*n^2
    假设对于 m<n ，总有 T(m) ≤ c*m^2
    即 T(n-1) ≤ c*(n-1)^2
    那么
    T(n) ≤ c*(n-1)^2 + n
        ≤ c*n^2 - c*2n + c + n
        ≤ c*n^2 - (c*2n - c -n)
        ≤ c*n^2 - ((n-1)c + (c-1)n)
    由于 n>1 && c>0 则 ((n-1)c + (c-1)n) > 0
    故 T(n) ≤ c*n^2
    得 T(n) = O(n^2)

变形的换元解法

求解：

这里可以假设n开方后是整数。
令 m=lgn得到
    T(2^m) = 2T(2^(m/2)) + m
使 S(m) = T(2^m), 则
    S(m) = 2S(m/2) + m
这里的递归式S(m)就可以使用与上面相同的解法。
    猜测 S(m) = O(mlgm)， 即存在常数c>0,可得 S(m) ≤ cmlgm
    假设c>0时对于任意的 a<m 都有S(a) ≤ calga
    则 S(m/2) ≤ c(m/2)lg(m/2)
    S(m) ≤ 2c(m/2)lg(m/2) + m
         ≤ cmlgm - m(c-1)
         ≤ cmlgm
    所以 S(m) = O(mlgm)
T(n)=T(2^m)=S(m)=O(mlgm)=O(lgn*lglgn)

二、递归树法

虽然可以用代入法简洁的证明一个解是递归式的正确解，但想出一个好的猜测可能并不容易。画出递归树是设计好的猜测的一种简单而直接的方法。

在递归树中，每个结点代表一个单一子问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价。再将所有层中的代价求和，得到递归调用总代价。

例

我们以为例。
如下图显示了构造递归树的必要步骤，为方便起见，假定n是4的幂。

递归树法存在一定误差，需要注意

三、主方法

主方法为如下形式的递归式提供了特别的解法
** T(n) = aT(n/b) + f(n) **
其中a,b是常数， a≥1, b>1,f(n)是渐近正函数

主方法依赖这些定理

主方法概括

比较 和 f(n)，如果f(n)的复杂度较大，T(n)=O(f(n)),如果f(n)的复杂度较小，则T(n)=O()。
而若二者相等，则T(n)=O( * lgn)

举例

T(n) = 7T(n/2) + O(n^2)

这里有a=7,b=2,f(n)=n^2。
因此 > f(n)
则 T(n) = O(n ^ (lg 7))

the end

欢迎友善交流。