时间:2017年2月6日 天气:阴:cloud:
Author:冬之晓:angry:
Email: 347916416@qq.com
前天，我回到焦作，腾飞叫晨辰帮忙把东西搬过来，顺便住了一夜，昨天早晨，晨辰就回去了，因为他在家也待不了多久，
最多到正月十五。一上班回家时间就少了。让他专门过来给我们送东西真的是不好啥意思。下午，腾飞说想锻炼身体，
于是晚上吃饭的时候我们顺便找了一家健身房。并且准备第二天去，今天中午，我就和腾飞一起去了健身房，锻炼了20min，
感觉效果不错，下午学习精神多啦，以后有机会还要去锻炼身体！
这一段时间，我研究了一下算法的时间复杂度分析，感觉其中的递归分析挺有意思，就总结一下记录下来，以备以后随时复习查看。
下面假设递归方程式已经给出了，仅仅说明如何计算递归方程的时间复杂度。 对于递归方程的时间复杂度分析，需要分为两个步骤，计算和证明
一、步骤一:计算
遇到一个递归方程，首先看这个递归方程的形式，根据不同的形式又分为两种不同的计算方法：
1.形式如：T(n)=aT(nb)+f(n)的递归函数
对于形如T(n)=aT(nb)+f(n)的递归函数，我们可以使用下面的公式进行计算其时间复杂度：
T(n)={O(nlogab),O(nlogab)>O(f(n))O(f(n)×logn),O(nlogab)=O(f(n))O(f(n),O(nlogab)<O(f(n))注意：上面的公式中a>1,b>1均为正数，f(n)为确定的正函数。
2.形式如：T(n)=C1T(n−1)+C2T(n−2)+⋯+CkT(n−k)+f(n)的递归函数
对于形如T(n)=C1T(n−1)+C2T(n−2)+⋯+CkT(n−k)+f(n)的递归函数，要求其中C1,C2,…,Ck≠0的常数，同时会有k个已知的等式E1,E2,…,Ek组成形如下面的递归函数：
T(n)={E1,n=0E2,n=1E3,E4…Ek−1n=2,3…k−2Ek,n=k−1C1T(n−1)+C2T(n−2)+⋯+CkT(n−k)+f(n),n>k−1首先从递归式
T(n)=C1T(n−1)+C2T(n−2)+⋯+CkT(n−k)+f(n)入手，将该递归式式移项得：
T(n)−C1T(n−1)−C2T(n−2)−⋯−CkT(n−k)=f(n)然后写出其对应的齐次方程，即根据含有T(n),T(n−1),T(n−2),…,T(n−k)的个数减去1来确定方程未知数的最大次数为k，然后将方程中的T(n)改为未知数的最大次数，T(n−1)改为未知数的第二大次数，以此类推， 假设齐次方程的未知数是t，则结果如下式：
tk−C1tk−1−C2tk−2−⋯−Ck=f(n)根据该方程的形式，可以知道如果该方程的某个解t=r是m重根，则m个解的形式是{rn,nrn,n2rn,…,nm−1rn}，如果剩余的解有多重跟也按照这种形式写出即可，为了简便，假设剩余的解都为单根， 则还剩(k−m)个解，其解的形式是{rn1,rn2,…,rnk−m}，然后假设每个解的形式对应的系数分别为a1,a2,…,ak，则可以写出齐次方程的通解形式：
a1rn+a2nrn+a3n2rn+…+amnm−1rn+am+1rn1+am+2rn1+…+akrnk−m为了求解通解中的未知系数a1,a2,…,ak，需要先求的齐次方程的特解，下面给出特解形式表格，为了简便，令C(t)=T(n)−C1T(n−1)−C2T(n−2)−⋯−CkT(n−k)
| f(n)形式 | 条件 | 特解形式 |
|---|---|---|
| an | C(a)≠0 ———————- a是C(t)的m重根 |
p0an ———– p0nman |
| ns | C(1)≠0 ———————- 1是C(t)的m重根 |
p0+p1n+p2n2+…+psns ————————————————– nm(p0+p1n+p2n2+…+psns) |
| nsan | C(a)≠0 ———————- a是C(t)的m重根 |
(p0+p1n+p2n2+…+psns)an —————————————————- nm(p0+p1n+p2n2+…+psns)an |
| 常数 | 无 | 常数x |
注意：这个表格中需要求的未知数是：p0,p1,…,ps,x，根据f(n)形式和条件在表中找到对应的特解形式———假设特解形式为M，令T(n)=M回代入到递归方程T(n)=C1T(n−1)+C2T(n−2)+⋯+CkT(n−k)+f(n)中， 求出未知数p0,p1,…,ps,x，将这些未知数代回特解中，即得到特解的确定形式，设其确定形式是ζ，则可以写出其次方程的“通解+特解”形式：
a1rn+a2nrn+a3n2rn+…+amnm−1rn+am+1rn1+am+2rn1+…+akrnk−m+ζ最后将递归方程的k个已知的等式E1,E2,…,Ek代入“通解+特解”形式，解出未知系数a1,a2,…,ak，回代入“通解+特解”形式即得到最终解。
二、步骤二:证明
将第一步算出的时间复杂度带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明即可。
三、举例说明
以后再加上……
