数据结构与算法Day20----递归算法时间复杂度的求解方法

一、递归算法时间复杂度的求解方法：

1、求解思路：

递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。如果把这个一层一层的分解过程画成图，它其实就是一棵树。给这棵树起一个名字，叫作递归树。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。

二、举例：

1、分析快速排序的时间复杂度：

<1>、根据递归树求解时间复杂度方法：

假设平均情况下，每次分区之后，两个分区的大小比例为 $1:k$ 。当 $k=9$ 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 $T(n)=T(\frac{n}{10})+T(\frac{9n}{10})+n$ 。这个公式可以推导出时间复杂度，但是推导过程非常复杂。
如果采取递归树的方法，还是取 $k$ 等于 $9$ ，也就是说，每次分区都很不平均，一个分区是另一个分区的 $9$ 倍。快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 $n$ 。
现在只要求出递归树的高度 $h$ ，这个快排过程遍历的数据个数就是 $h * n$ ，就是说，时间复杂度就是 $O(h * n)$ 。因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。这样一个递归树的高度是多少呢？因为快速排序结束的条件就是待排序的小区间，大小为 $1$ ，也就是说叶子节点里的数据规模是 $1$ ，从根节点 $n$ 到叶子节点 $1$ ，递归树中最短的一个路径每次都乘以 $\frac{1}{10}$ ，最长的一个路径每次都乘以 $\frac{9}{10}$ 。通过计算可以得到，从根节点到叶子节点的最短路径是 $\log_{10}n$ ，最长的路径是 $\log_{\frac{10}{9}}n$ 。
所以，遍历数据的个数总和就介于 $n\log_{10}n$ 和 $n\log_{\frac{10}{9}}n$ 之间。根据复杂度的大O表示法，对数复杂度的底数不管是多少，统一写成 $\lg{}n$ ，所以，当分区大小比例是 $1:9$ 时，快速排序的时间复杂度仍然是 $O(n\log n)$ 。
刚刚假设 $k=9$ ，那如果 $k=99$ ，也就是说，每次分区极其不平均，两个区间大小是 $1:99$ ，这个时候的时间复杂度是多少呢？可以类比上面 $k=9$ 的分析。当 $k=99$ 的时候，树的最短路径就是 $\log_{100}n$ ，最长路径是 $\log_{\frac{100}{99}}n$ ，所以总遍历数据个数介于 $n\log_{100}n$ 和 $n\log_{\frac{100}{99}}n$ 之间。尽管底数变了，但是时间复杂度也仍然是 $O(n\log n)$ 。也就是说，对于 $k$ 等于 $9$ ， $99$ ，甚至是 $999$ ， $9999$ ……，只要 $k$ 的值不随 $n$ 变化，是一个事先确定的常量，那快排的时间复杂度就是 $O(n\log n)$ 。所以，从概率论的角度来说，快排的平均时间复杂度就是 $O(n\log n)$ 。

<2>、递归树：

快速排序递归树

2、分析斐波那契数列的时间复杂度：

<1>、根据递归树求解时间复杂度方法：

$f(n)$ 分解为 $f(n-1)$ 和 $f(n-2)$ ，每次数据规模都是 $-1$ 或者 $-2$ ，叶子节点的数据规模是 $1$ 或者 $2$ 。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 $-1$ ，那最长路径大约就是 $n$ ；如果每次都是 $-2$ ，那最短路径大约就是 $\frac{n}{2}$ 。
每次分解之后的合并操作只需要一次加法运算，把这次加法运算的时间消耗记作 $1$ 。所以，从上往下，第一层的总时间消耗是 $1$ ，第二层的总时间消耗是 $2$ ，第三层的总时间消耗就是 $2^{2}$ 。依次类推，第 $k$ 层的时间消耗就是 $2^{k-1}$ ，那整个算法的总的时间消耗就是每一层时间消耗之和。
如果路径长度都为 $n$ ，那这个总和就是 $2^{n}-1$ 。
如果路径长度都是 $\frac{n}{2}$ ，那整个算法的总的时间消耗就是 $2^{\frac{n}{2}}-1$ 。
所以，这个算法的时间复杂度就介于 $O(2^{n})$ 和 $O(2^{\frac{n}{2}})$ 之间。虽然这样得到的结果还不够精确，只是一个范围，但是基本上知道了上面算法的时间复杂度是指数级的。

<2>、递归树：

斐波拉契数列递归树

3、分析全排列的时间复杂度：

<1>、根据递归树求解时间复杂度方法：

第一层分解有 $n$ 次交换操作，第二层有 $n$ 个节点，每个节点分解需要 $n-1$ 次交换，所以第二层总的交换次数是 $n*(n-1)$ 。第三层有 $n*(n-1)$ 个节点，每个节点分解需要 $n-2$ 次交换，所以第三层总的交换次数是 $n*(n-1)*(n-2)$ 。
以此类推，第 $k$ 层总的交换次数就是 $n * (n-1) * (n-2) * … * (n-k+1)$ 。最后一层的交换次数就是 $n * (n-1) * (n-2) * … * 2 * 1$ 。每一层的交换次数之和就是总的交换次数。
这个公式的求和比较复杂，看最后一个数， $n * (n-1) * (n-2) * … * 2 * 1$ 等于 $n!$ ，而前面的 $n-1$ 个数都小于最后一个数，所以，总和肯定小于 $n * n!$ ，也就是说，全排列的递归算法的时间复杂度大于 $O(n!)$ ，小于 $O(n * n!)$ ，虽然不是非常精确的时间复杂度，但是这样一个范围已经说明全排列的时间复杂度是非常高的。