［数据结构］递归树：借助树求解递归算法的时间复杂度

r囧r小猫 2022-03-10 07:48 372阅读 0赞

### 文章目录 ###

*  递归树与时间复杂度分析
 *   *   *  实战一：分析快速排序的时间复杂度
         *  实战二：分析斐波那契数列的时间复杂度
         *  实战三：待补充，先学其他的．．．

# 递归树与时间复杂度分析 #

我们前面讲过，递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。

如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作**递归树**。这里画了一棵斐波那契数列的递归树，你可以看看。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]  
OK,那么这里就有一个问题：F(5),F函数执行了多少次？　9次

那么**如何使用其来求解递归的时间复杂度呐？**

归并排序算法你还记得吧？它的递归实现代码非常简洁。现在我们就借助归并排序来看看，如何用递归树，来分析递归代码的时间复杂度。

// 归并排序算法, A 是数组，n 表示数组大小
    merge_sort(A, n) { 
      merge_sort_c(A, 0, n-1)
    }
    
    // 递归调用函数
    merge_sort_c(A, p, r) { 
      // 递归终止条件
      if p >= r  then return
    
      // 取 p 到 r 之间的中间位置 q
      q = (p+r) / 2
      // 分治递归
      merge_sort_c(A, p, q)
      merge_sort_c(A, q+1, r)
      // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
      merge(A[p...r], A[p...q], A[q+1...r])
    }

例题：  
148. 排序链表  
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3  
输出: 1->2->3->4  
示例 2:

输入: -1->5->3->4->0  
输出: -1->0->3->4->5

解析：[排序算法总结与几道排序题][Link 1]

归并排序的原理我就不详细介绍了，如果你忘记了，可以回看一下第 12 节的内容。归并排序每次会将数据规模一分为二。我们把归并排序画成递归树，就是下面这个样子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]  
因为每次分解都是一分为二，所以代价很低，我们把时间上的消耗记作常量 11。归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中我们可以看出，**每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关(这里需要注意的是每一层，而不是所有的，因为2，2合并为4，下层就是4，4合并为8)**。我们把每一层归并操作消耗的时间记作 `n`。

现在，我们只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 `O(n∗h)`。

从归并排序的原理和递归树，可以看出来，归并排序递归树是一棵**满二叉树**。我们前两节中讲到，满二叉树的高度大约是 **`log2n`(这个我有时间再总结一下，算过，但记不得了**)，所以，归并排序递归实现的时间复杂度就是 `O(nlogn)`。我这里的时间复杂度都是估算的，对树的高度的计算也没有那么精确，但是这并不影响复杂度的计算结果。

利用递归树的时间复杂度分析方法并不难理解，关键还是在实战，所以，接下来我会通过三个实际的递归算法，带你实战一下递归的复杂度分析。

### 实战一：分析快速排序的时间复杂度 ###

在用递归树推导之前，我们先来回忆一下用递推公式的分析方法。你可以回想一下，当时，我们为什么说用递推公式来求解平均时间复杂度非常复杂？

快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 `T(n)=2T(n2)+nT(n)=2T(n2)+n`，很容易就能推导出时间复杂度是 `O(nlogn)`。但是，我们并不可能每次分区都这么幸运，正好一分为二。

--------------------

> 如何使用递推公式计算时间复杂度?：

在递归那一节我们讲过，递归的适用场景是，一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，我们再把 b、c 的结果合并成 a 的结果。

如果我们定义求解问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，那我们就可以得到这样的递推关系式：  
`T(a) = T(b) + T(c) + K`  
其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。

从刚刚的分析，我们可以得到一个重要的结论：**不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。**

套用这个公式，我们来分析一下归并排序的时间复杂度。

我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，**归并排序的时间复杂度的计算公式**就是：

T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。 
    
    T(n) = 2*T(n/2) + n； n>1

通过这个公式，如何来求解 T(n) 呢？还不够直观？那我们再进一步分解一下计算过程。

T(n) = 2*T(n/2) + n 
    		= 2*(2*T(n/4) + n/2) + n 
    		= 4*T(n/4) + 2*n 
    		= 4*(2*T(n/8) + n/4) + 2*n 
    		= 8*T(n/8) + 3*n 
    		= 8*(2*T(n/16) + n/8) + 3*n 
    		= 16*T(n/16) + 4*n
    		 ...... 
    		= 2^k * T(n/2^k) + k * n
    		 ......

通过这样一步一步分解推导，我们可以得到 `T(n) = 2^kT(n/2^k)+kn`。当 `T(n/2^k)=T(1)` 时，也就是 `n/2^k=1`，我们得到 `k=log2n` 。我们将 k 值代入上面的公式，得到 `T(n)=Cn+nlog2n` 。如果我们用大 O 标记法来表示的话，T(n) 就等于 `O(nlogn)`。所以归并排序的时间复杂度是 O(nlogn)。

--------------------

我们假设平均情况下，每次分区之后，两个分区的大小比例为 `1:k`。当 `k=9` 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 `T(n)=T(n/10)+T(9n/10)+n`。

这个公式可以推导出时间复杂度，但是推导过程非常复杂。那我们来看看，用递归树来分析快速排序的平均情况时间复杂度，是不是比较简单呢？ 我们还是取 k 等于 9，也就是说，每次分区都很不平均，一个分区是另一个分区的 9 倍。如果我们把递归分解的过程画成递归树，就是下面这个样子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]  
快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 n。我们现在只要求出递归树的高度 h，这个快排过程遍历的数据个数就是`h∗n`，也就是说，时间复杂度就是 `O(h∗n)`。

因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。这样一个递归树的高度是多少呢？

我们知道，快速排序结束的条件就是待排序的小区间，大小为 1，也就是说叶子节点里的数据规模是 1。从根节点 n 到叶子节点 1，递归树中最短的一个路径每次都乘以 1/10，最长的一个路径每次都乘以 9/10。(**其实就是说：快排结束的最终结果取决于分成大的那一部分**)通过计算，我们可以得到，**从根节点到叶子节点的最短路径是 `log10n`，最长的路径是 `log10/9n`。**(如何算出来的，有点不明白，先当结论记吧！！！)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]  
所以，遍历数据的个数总和就介于 `nlog10n`和 `nlog10/9n` 之间。根据复杂度的大 O 表示法，对数复杂度的底数不管是多少，我们统一写成 `logn`，所以，当分区大小比例是 1:9 时，快速排序的时间复杂度仍然是 O(nlogn)。

### 实战二：分析斐波那契数列的时间复杂度 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]  
这棵递归树的高度是多少呢？

f(n) 分解为 f(n−1) 和 f(n−2)，每次数据规模都是 −1 或者 −2，叶子节点的数据规模是 1或者2。所以，从根节点走到叶子节点，每条路径是长短不一的。**如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −2，那最短路径大约就是 n／2。**

**每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作 1**。所以，从上往下，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 `2^2`。(**满二叉树**)依次类推，第 k 层的时间消耗就是 `2^k−1`，那整个算法的总的时间消耗就是每一层时间消耗之和。

如果路径长度都为 n，那这个总和就是 `2^n−1`(对应最长路径)  
如果路径长度都为 2/n，那这个总和就是 `2^2/n−1`（对应最短路径）

所以，这个算法的时间复杂度就介于 O(2^n) 和 `O(2^n/2)` 之间。虽然这样得到的结果还不够精确，只是一个范围，但是我们也基本上知道了上面算法的时间复杂度是指数级的，非常高。

### 实战三：待补充，先学其他的．．． ###

参考极客时间：[数据结构与算法之美][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]: /images/20220310/87af6db103cb4dc797b841f82c013214.png
[Link 1]: https://blog.csdn.net/liushengxi_root/article/details/84886544
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]: /images/20220310/7b1cf5d769524d8daa076550141f9a69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]: /images/20220310/870422554fbd499499aac14aa9ada4ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]: /images/20220310/c1feea75c14841faafbe42363b58c593.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]: /images/20220310/d9573ca3ea9b47f9bf63baa093aa1977.png
[Link 2]: https://time.geekbang.org/column/article/69388