递推关系式的一般式的求解
一、线性齐次递推式的求解
形如 f(n)=a1f(n-1)+....+akf(n-k)的递推式(注意没有常数项)称为齐次递推式
我们只考虑1阶和2阶的情况：
一阶 f(n)=af(n-1),则递推式为 f(n)=af(n-1)=a2f(n-2)...=anf(0)
二阶 f(n)=a1f(n-1)+a2f(n-2), 则特征方程变为 x2-a1x-a2, 令方程的根为r1,r2,则递推式的解为
f(n)=c1r1^n+c2r2^n if r1!=r2 OR f(n)=c1r^n+c2*n*r^n if r1==r2
*这个可以推Fibonacci数列的表达式！
二、非齐次递推式的求解
主要将考虑三种形式的非齐次的递推式
形式1： f(n)=f(n-1)+g(n) 解为 f(n)=f(0)+Σ{i=1~n}g(i)
形式2: f(n)=g(n)f(n-1) n>=1 解为 f(n)=g(n)g(n-1)....g(1)f(0)
形式3： f(n)=g(n)f(n-1)+h(n) n>=1
其解法是特殊的： 定义一个新函数 f'(n),令 f(n)=g(n)g(n-1)...g(1)f'(n), n>=1; f'(0)=f(0)
则 可得到 f(n-1)与f'(n-1)的关系，带入形式3得到 g(n)....g(1)f'(n)=g(n){g(n-1)...g(1)f'(n-1)}+h(n)
即 f'(n)=f'(n-1)+h(n)/{g(n).....g(1)}; f'(n)=f'(0)+SIGMA{i=1~n}(h(i)/g(i)....g(1));
最终得到 f(n)=g(n)....g(1){f(0)+SIGMA{i=1~n}(h(i)/g(i)....g(1))};
Master Theorem(非常重要的定理，由递推关系式得到此函数的复杂度) (这个在算法导论中也有介绍)：
Let a>=1, c>1 be constants, f(n) be a function, T(n) be defined on the negative integers by the recurrence
T(n)=aT(n/c)+f(n) where we intepret n/c to mean either ceil(n/c) or floor(n/c). Then
1) If f(n)=O(n^(logca-ε)) for some ε>0, then T(n)=Θ(n^logca)
2) If f(n)=Θ(n^logca), then T(n)=Θ(n^logca)logn
3) If f(n)=Ω(n^(logca+ε)) for some ε>0 and if a*f(n/c)≤kf(n) for some constant k<1 and all sufficiently large n, then T(n)=Θ(f(n))
!!注意 这三种情况并不是完全覆盖，也就是存在这个定理无法分析的情况!!
Exercise: (1) T(n)=9T(n/3)+n (2) T(n)=3T(n/4)+nlogn (3) T(n)=T(2n/3)+1 (4) T(n)=2T(n/2)+nlogn