时间:2017年2月6日 天气:阴:cloud:
Author:冬之晓:angry:
Email: 347916416@qq.com
前天，我回到焦作，腾飞叫晨辰帮忙把东西搬过来，顺便住了一夜，昨天早晨，晨辰就回去了，因为他在家也待不了多久，
最多到正月十五。一上班回家时间就少了。让他专门过来给我们送东西真的是不好啥意思。下午，腾飞说想锻炼身体，
于是晚上吃饭的时候我们顺便找了一家健身房。并且准备第二天去，今天中午，我就和腾飞一起去了健身房，锻炼了20min，
感觉效果不错，下午学习精神多啦，以后有机会还要去锻炼身体！
这一段时间，我研究了一下算法的时间复杂度分析，感觉其中的递归分析挺有意思，就总结一下记录下来，以备以后随时复习查看。
下面假设递归方程式已经给出了，仅仅说明如何计算递归方程的时间复杂度。 对于递归方程的时间复杂度分析，需要分为两个步骤，计算和证明
一、步骤一:计算
遇到一个递归方程，首先看这个递归方程的形式，根据不同的形式又分为两种不同的计算方法：
1.形式如：的递归函数
对于形如的递归函数，我们可以使用下面的公式进行计算其时间复杂度：
注意：上面的公式中均为正数，为确定的正函数。
2.形式如：的递归函数
对于形如的递归函数，要求其中的常数，同时会有个已知的等式组成形如下面的递归函数：
首先从递归式
入手，将该递归式式移项得：
然后写出其对应的齐次方程，即根据含有的个数减去1来确定方程未知数的最大次数为，然后将方程中的改为未知数的最大次数，改为未知数的第二大次数，以此类推， 假设齐次方程的未知数是，则结果如下式：
根据该方程的形式，可以知道如果该方程的某个解是重根，则个解的形式是，如果剩余的解有多重跟也按照这种形式写出即可，为了简便，假设剩余的解都为单根， 则还剩个解，其解的形式是，然后假设每个解的形式对应的系数分别为，则可以写出齐次方程的通解形式：
为了求解通解中的未知系数，需要先求的齐次方程的特解，下面给出特解形式表格，为了简便，令
| 形式 | 条件 | 特解形式 |
|---|---|---|
| ———————- 是的重根 |
———– |
|
| ———————- 是的重根 |
————————————————– |
|
| ———————- 是的重根 |
—————————————————- |
|
| 常数 | 无 | 常数 |
注意：这个表格中需要求的未知数是：，根据形式和条件在表中找到对应的特解形式———假设特解形式为，令回代入到递归方程中， 求出未知数，将这些未知数代回特解中，即得到特解的确定形式，设其确定形式是，则可以写出其次方程的“通解+特解”形式：
最后将递归方程的个已知的等式代入“通解+特解”形式，解出未知系数，回代入“通解+特解”形式即得到最终解。
二、步骤二:证明
将第一步算出的时间复杂度带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明即可。
三、举例说明
以后再加上……
