本文共 5188 字,大约阅读时间需要 17 分钟。
递归树与时间复杂度分析
我们知道,递归代码的时间复杂度分析起来很麻烦。除了可以使用递推公式这种比较复杂的分析方法外,还可以借助递归树来分析递归算法的时间复杂度。
递归的思想就是,将大问题分解为小问题来求解,然后再将小问题分解为小小问题。这样一层一层的分解,直到问题的数据规模被分解得足够小,不用继续递归分解位置。
如果我们把这个一层一层的分解过程画成图,它其实就是一棵树。我们给这棵树起一个名字,叫做递归树。如下图为一颗棵斐波那契数列的递归树,节点里的数字表示数据的规模,一个节点的求解可以分解为左右子节点两个问题的求解。
分析快速排序的时间复杂度
为什么说用递推公式来求解平均时间复杂度非常复杂
-
快排在最好情况下,每次分区都能一分为二,这个时候用递推公式 T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\frac{n}{2}) + n T(n)=2T(2n)+n,很容易就能推导出时间复杂度是 O ( n l o g n ) O(n log n) O(nlogn)。但是,我们并不可能每次分区都这么幸运,正好一分为二。
-
我们假设平均情况下,每次分区之后,两个分区的大小比例为 。当 时,如果用递推公式的方法来求解时间复杂度的话,递推公式就写成 T ( n ) = T ( n 10 ) + T ( 9 n 10 ) + n T(n) = T(\frac{n}{10} ) + T(\frac{9n}{10} ) + n T(n)=T(10n)+T(109n)+n。
这个公式可以推导出时间复杂度,但是推导过程非常复杂。
用递归树来简化快排的平均复杂度为例
- 我们还是取k等于9,也就是说,每次分区都很不平均,一个分区是另一个分区的9倍。如果我们把递归分解的过程画成递归树,如下图:
- 快排中,每次分区都要遍历待分区区间的所有数据,所以,每一层分区操作所遍历的个数之和就是n。我们现在只要求出递归树的高度h,这个快排过程遍历的数据个数就是h*n,也就是说 O ( n ∗ h ) O(n*h) O(n∗h)
因为每次分区并不是均匀的一分为二,所以递归树并不是满二叉树。这样一个递归树的高度是多少呢?
- 我们知道,快排结束的条件就是待排序的小区间,大小为1,也就是说叶子节点里的数据规模是1.从根节点n到叶子节点1,递归树中最短的一个路径每次都乘以 1 10 \frac{1}{10} 101,最长的一个路径每次都乘以 9 10 \frac{9}{10} 109。通过计算,我们可以得到,从根节点到叶子节点的最短路径是 l o g 10 n log_{10}n log10n,最长的路径是 l o g 10 9 n log_{\frac{10}{9}n} log910n
- 所以,遍历数据的个数就介于 n l o g 10 n nlog_{10}n nlog10n和 n l o g 10 9 n nlog_{\frac{10}{9}n} nlog910n之间。根据复杂度的大0表示法,对数复杂度的底数不管是多少,我们统一写成 l o g n logn logn。所以,当分区大小比例是1:9时,快速排序的时间复杂度仍然是 O ( n l o g n ) O(n log n) O(nlogn)
刚刚我们假设 ,那如果 ,也就是说,每次分区极其不平均,两个区间大小是 ,这个时候的时间复杂度是多少呢?
- 我们可以类比上面 的分析过程。当 的时候,树的最短路径就是 l o g 100 n log_{100}n log100n,最长的路径是 l o g 100 99 n log_{\frac{100}{99}n} log99100n
- 所以总遍历数据个数介于 n l o g 100 n nlog_{100}n nlog100n和 n l o g 100 99 n nlog_{\frac{100}{99}n} nlog99100n之间。尽管底数变了,快速排序的时间复杂度仍然是 O ( n l o g n ) O(n log n) O(nlogn)
也就是说,对于k等于 9,99 ,甚至是999 ,9999 ……,只要k的值不随n变化,是一个事先确定的常量,那快排的时间复杂度就是 O ( n l o g n ) O(n log n) O(nlogn)。所以,从概率学的角度来说,快排的时间复杂度就是 O ( n l o g n ) O(n log n) O(nlogn)
分析归并排序的时间复杂度
如下图,归并排序每次会将数据规模一分为二。其递归树如下:
- 因为每次分解都是一分为二,所以代价很低,我们把时间上的消耗记为常量1。归并算法中比较耗时的是归并操作,也就是两个子数组合并为大数组。从图中我们可以看出,每一层归并操作消耗的时间总和是一样的,跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记为n。
- 现在,我们只需要知道这棵树的高度h,用高度h乘以每一层的时间消耗n,就可以得到总的时间复杂度 O ( n ∗ h ) O(n*h) O(n∗h)
- 从归并排序的原理和递归树可以看出来,归并排序递归树是一颗满二叉树。满二叉树的高度是 l o g 2 n log_2n log2n。所以,归并排序实现的时间复杂度就是 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)。
分析斐波那契数列的时间复杂度
对于斐波那契数列:
int f(int n) { if (n == 1) return 1; if (n == 2) return 2; return f(n-1) + f(n-2);}
其递归树为:
这棵递归树的高度是多少呢?- f ( n ) f(n) f(n)分解为 f ( n − 1 ) f(n-1) f(n−1)和 f ( n − 2 ) f(n-2) f(n−2),每次数据规模都是-1或者-2,叶子节点的数据规模是1或者2,。所以,从根节点走到叶子节点,每条路径是长短不一的。如果每次都是-1,那么最长路径大约就是n;如果每次都是-2,那最短路径大约是 n 2 \frac{n}{2} 2n
- 每次分解之后的合并操作只需要一次加法运算,我们把这次加法运算的时间消耗记作1.所以,从上往下,第一层的总时间消耗是1,第二次的总时间消耗是2,第三层的总时间消耗就是 2 2 2^2 22。依次类推,第 k k k层的时间消耗是 2 k − 1 2^{k-1} 2k−1,那整个顺丰的总时间消耗就是每一层时间消耗之和。
- 如果路径长度都为n,那么这个总和就是 2 n − 1 2^n - 1 2n−1
- 如果路径长度都为 n 2 \frac{n}{2} 2n,那整改算法的总的时间消耗是 2 n 2 − 1 2^{\frac{n}{2}}-1 22n−1
所以,这个算法的时间复杂度就介 O ( 2 n ) O(2^n) O(2n) 和 O ( 2 n 2 ) O(2^{\frac{n}{2}}) O(22n)之间。虽然这样得到的结果还不够精确,只是一个范围,但是我们也基本上知道了上面算法的时间复杂度是指数级的,非常高。
分析全排列的时间复杂度。
所谓全排列就是“如何把n个数据的所有排列都找出来”。
举个例子,比如, 1、2、3这样3个数据,有下面这几种不同的排列:
1, 2, 31, 3, 22, 1, 32, 3, 13, 1, 23, 2, 1
如何编程打印一组数据的所有排列呢?这里就可以用递归来实现。
如果我们确定了最后一位数据,那就变成了求解剩下n-1个数据的排列问题。而最后一位数据可以是n个数据中的任意一个,因为它的取值就有n中情况、所以“n个数据的排列”问题,就可以分解成n个“n-1个数据的排列的”的子问题。
递推公式如下:
假 设 数 组 中 存 储 的 是 1 , 2 , 3... n 假设数组中存储的是 1,2, 3...n 假设数组中存储的是1,2,3...n f ( 1 , 2 , . . . n ) = 最 后 一 位 是 1 , f ( n − 1 ) + 最 后 一 位 是 2 , f ( n − 1 ) + . . . + 最 后 一 位 是 n , f ( n − 1 ) 。 f(1,2,...n) = {最后一位是 1, f(n-1)} + {最后一位是 2, f(n-1)} +...+{最后一位是 n, f(n-1)}。 f(1,2,...n)=最后一位是1,f(n−1)+最后一位是2,f(n−1)+...+最后一位是n,f(n−1)。代码为:
public class Main { // k 表示要处理的子数组的数据个数 public static void printPermutations(int [] data, int n, int k){ if(k == 1){ for (int i = 0; i < n; ++i){ System.out.print(data[i] + " "); } System.out.println(); } for (int i = 0; i < k; ++i){ int tmp = data[i]; data[i] = data[k - 1]; data[k - 1] = tmp; printPermutations(data, n, k - 1); tmp = data[i]; data[i] = data[k-1]; data[k-1] = tmp; } } public static void main(String[] args) { int[]a ={ 1, 2, 3, 4}; printPermutations(a, 4, 4); }}
时间复杂度分析:
- 首先,我们还是画出递归树。不过,现在的递归树已经不是标准的二叉树了。
- 第一层分解有 n n n次交换操作,第二层有n个节点,每个节点分解需要n-1次交换,所以第二层总的交换次数是 n ∗ ( n − 1 ) n * (n-1) n∗(n−1)。第三层有 n ∗ ( n − 1 ) n * (n-1) n∗(n−1)个节点,每个节点需要n-2次交换,所以第三层总的交换次数是 n ∗ ( n − 1 ) ∗ ( n − 2 ) n * (n-1) * (n - 2) n∗(n−1)∗(n−2)
- 以此类推,第 k 层总的交换次数就是 n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ … ∗ ( n − k + 1 ) n∗(n−1)∗(n−2)∗…∗(n−k+1) 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−2)∗…∗2∗1。每一层的交换之和就是总的交换次数。 n + n ∗ ( n − 1 ) + n ∗ ( n − 1 ) ∗ ( n − 2 ) + . . . + n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ . . . ∗ 2 ∗ 1 n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1 n+n∗(n−1)+n∗(n−1)∗(n−2)+...+n∗(n−1)∗(n−2)∗...∗2∗1
- 这个公式的求和比较复杂,我们看最后一个数, n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ … ∗ 2 ∗ 1 n∗(n−1)∗(n−2)∗…∗2∗1 n∗(n−1)∗(n−2)∗…∗2∗1等于n!,而前面的 n−1 个数都小于最后一个数,所以,总和肯定小于 n ∗ n ! n∗n! n∗n!,也就是说,全排列的递归算法的时间复杂度大于 O ( n ! ) O(n!) O(n!),小于 O ( n ∗ n ! ) O(n∗n!) O(n∗n!)
虽然我们没法知道非常精确的时间复杂度,但是这样一个范围已经让我们知道,全排列的时间复杂度是非常高的。
转载地址:https://blog.csdn.net/zhizhengguan/article/details/122435493 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!