浙江省建设政务网站,百度搜索风云榜单,大庆市建设局网站上不去,东莞莞城网站建设目录 前言递归树与时间复杂度分析实战一#xff1a;分析快速排序的时间复杂度实战二#xff1a;分析斐波那契数列的时间复杂度实战三#xff1a;分析全排列的时间复杂度内容小结 前言 本节课程思维导图#xff1a; 今天#xff0c;我们来讲这种数据结构的一种特殊应用分析快速排序的时间复杂度实战二分析斐波那契数列的时间复杂度实战三分析全排列的时间复杂度内容小结 前言 本节课程思维导图 今天我们来讲这种数据结构的一种特殊应用递归树。 我们都知道递归代码的时间复杂度分析起来很麻烦。除了用递推公式这种比较复杂的分析方法有没有更简单的方法呢今天我们就来学习另外一种方法借助递归树来分析递归算法的时间复杂度。
递归树与时间复杂度分析
递归的思想就是将大问题分解为小问题来求解然后再将小问题分解为小小问题。这样一层一层地分解直到问题的数据规模被分解得足够小不用继续递归分解为止。 如果我们把这个一层一层的分解过程画成图它其实就是一棵树。我们给这棵树起一个名字叫作递归树。我这里画了一棵斐波那契数列的递归树你可以看看。节点里的数字表示数据的规模一个节点的求解可以分解为左右子节点两个问题的求解。 在我们就来看如何用递归树来求解时间复杂度。现在我们就借助归并排序来看看如何用递归树来分析递归代码的时间复杂度。 因为每次分解都是一分为二我们把时间上的消耗记作常量 1。归并算法中比较耗时的是归并操作也就是把两个子数组合并为大数组。从图中我们可以看出每一层归并操作消耗的时间总和是一样的跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。
现在我们只需要知道这棵树的高度 h用高度 h 乘以每一层的时间消耗 n就可以得到总的时间复杂度 O(n∗h)。
归并排序的原理和递归树可以看出来归并排序递归树是一棵满二叉树。我们前两节中讲到满二叉树的高度大约是 log2n所以归并排序递归实现的时间复杂度就是 O(nlogn)。
利用递归树的时间复杂度分析方法并不难理解关键还是在实战所以接下来我会通过三个实际的递归算法带你实战一下递归的复杂度分析。学完这节课之后你应该能真正掌握递归代码的复杂度分析。
实战一分析快速排序的时间复杂度
快速排序在最好情况下每次分区都能一分为二这个时候用递推公式 T(n)2T(2n)n很容易就能推导出时间复杂度是 O(nlogn)。 我们假设平均情况下每次分区之后两个分区的大小比例为 1:k。当 k9 时如果用递推公式的方法来求解时间复杂度的话递推公式就写成 那我们来看看用递归树来分析快速排序的平均情况时间复杂度是不是比较简单呢 快速排序的过程中每次分区都要遍历待分区区间的所有数据所以每一层分区操作所遍历的数据的个数之和就是 n。我们现在只要求出递归树的高度 h这个快排过程遍历的数据个数就是 h∗n 也就是说时间复杂度就是 O(h∗n)。 因为每次分区并不是均匀地一分为二所以递归树并不是满二叉树。这样一个递归树的高度是多少呢 我们知道快速排序结束的条件就是待排序的小区间大小为 1也就是说叶子节点里的数据规模是 1。从根节点 n 到叶子节点 1递归树中最短的一个路径每次都乘以 1/10最长的一个路径每次都乘以 9/10。 通过计算我们可以得到从根节点到叶子节点的最短路径是 log 10 n \log_{10} n log10n最长的路径是 log 10 / 9 n \log_{10/9} n log10/9n。
实战二分析斐波那契数列的时间复杂度
int f(int n) {if (n 1) return 1;if (n 2) return 2;return f(n-1) f(n-2);
}我们先把上面的递归代码画成递归树就是下面这个样子 这棵递归树的高度是多少呢 如果路径长度都为 n那这个总和就是 2 n − 1 2^n−1 2n−1。 如果路径长度都是 n /2那整个算法的总的时间消耗就是 2 n / 2 − 1 2^{n/2}−1 2n/2−1
实战三分析全排列的时间复杂度
“如何把 n 个数据的所有排列都找出来”这就是全排列的问题。我来举个例子。比如123 这样 3 个数据有下面这几种不同的排列
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1如何编程打印一组数据的所有排列呢这里就可以用递归来实现。如果我们确定了最后一位数据那就变成了求解剩下 n−1 个数据的排列问题。而最后一位数据可以是 n 个数据中的任意一个因此它的取值就有 n 种情况。所以“n 个数据的排列”问题就可以分解成 n 个“n−1 个数据的排列”的子问题。 递推公式
假设数组中存储的是12 3...n。f(1,2,...n) {最后一位是1, f(n-1)} {最后一位是2, f(n-1)} ...{最后一位是n, f(n-1)}。如果我们把递推公式改写成代码就是下面这个样子
// 调用方式
// int[]a a{1, 2, 3, 4}; printPermutations(a, 4, 4);
// k表示要处理的子数组的数据个数
public 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;}
}现在我们来看下如何借助递归树轻松分析出这个代码的时间复杂度。首先我们还是画出递归树。不过现在的递归树已经不是标准的二叉树了。 第一层分解有 n 次交换操作第二层有 n 个节点每个节点分解需要 n−1 次交换所以第二层总的交换次数是 n∗(n−1)。第三层有 n∗(n−1) 个节点每个节点分解需要 n−2 次交换所以第三层总的交换次数是 n∗(n−1)∗(n−2)。以此类推第 k 层总的交换次数就是 n∗(n−1)∗(n−2)∗…∗(n−k1)。最后一层的交换次数就是 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∗n!也就是说全排列的递归算法的时间复杂度大于 O(n!)小于 O(n∗n!)虽然我们没法知道非常精确的时间复杂度但是这样一个范围已经让我们知道全排列的时间复杂度是非常高的。
内容小结
今天我们用递归树分析了递归代码的时间复杂度。加上之前的递推公式的时间复杂度分析方法我们现在已经学习了两种递归代码的时间复杂度分析方法了。 有些代码比较适合用递推公式来分析比如归并排序的时间复杂度、快速排序的最好情况时间复杂度有些比较适合采用递归树来分析比如快速排序的平均时间复杂度。而有些可能两个都不怎么适合使用比如二叉树的递归前中后序遍历。
