数据结构与算法整理总结---递归树

递归的思想就是,将⼤问题分解为⼩问题来求解,然后再将⼩问题分解为⼩⼩问题。这样⼀层⼀层地分解,直到问题的数据规模被分解得⾜够⼩,不⽤继续递归分解为⽌。

如果我们把这个⼀层⼀层的分解过程画成图,它其实就是⼀棵树。我们给这棵树起⼀个名字,叫作递归树。这⾥画了⼀棵斐波那契数列的递归树,你可以看看。节点⾥的数字表示数据的规模,⼀个节点的求解可以分解为左右⼦节点两个问题的求解。

数据结构与算法整理总结---递归树

通过这个例⼦,你对递归树的样⼦应该有个感性的认识了,看起来并不复杂。现在,我们就来看,如何⽤递归树来求解时间复杂度。

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

数据结构与算法整理总结---递归树

因为每次分解都是⼀分为⼆,所以代价很低,我们把时间上的消耗记作常量$1$。归并算法中⽐较耗时的是归并操作,也就是把两个⼦数组合并为⼤数组。从图中我们可以看出,每⼀层归并操作消耗的时间总和是⼀样的,跟要排序的数据规模有关。我们把每⼀层归并操作消耗的时间记作$n$。

现在,我们只需要知道这棵树的⾼度$h$,⽤⾼度$h$乘以每⼀层的时间消耗$n$,就可以得到总的时间复杂度$O(n*h)$。

从归并排序的原理和递归树,可以看出来,归并排序递归树是⼀棵满⼆叉树。,满⼆叉树的⾼度⼤约是$\log_{2}n$,所以,归并排序递归实现的时间复杂度就是$O(n\log n)$。这⾥的时间复杂度都是估算的,对树的⾼度的计算也没有那么精确,但是这并不影响复杂度的计算结果。

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

快速排序在最好情况下,每次分区都能⼀分为⼆,这个时候⽤递推公式$T(n)=2T(\frac{n}{2})+n$,很容易就能推导出时间复杂度是$O(n\log n)$。但是,我们并不可能每次分区都这么幸运,正好⼀分为⼆。

我们假设平均情况下,每次分区之后,两个分区的⼤⼩⽐例为$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表示法,对数复杂度的底数不管是多少,我们统⼀写成$\log n$,所以,当分区⼤⼩⽐例是$1:9$时,快速排序的时间复杂度仍然是$O(n\log n)$。

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

数据结构与算法整理总结---递归树

$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}})$之间。虽然这样得到的结果还不够精确,只是⼀个范围,但是我们也基本上知道了上⾯算法的时间复杂度是指数级的,⾮常⾼。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!