算法笔记(三):递归复杂度的计算、主定理、渐进符号 | 您所在的位置:网站首页 › 增长率的符号 › 算法笔记(三):递归复杂度的计算、主定理、渐进符号 |
有些同学可能会很困惑:时间复杂度的表示怎么一会儿是 大O, 一会儿是(读作Omega),一会儿又是(读作Theta)? 这三个符号略有区别,要用数学语言才能描述,略显枯燥,我们到后面再聊大O、、表示时间复杂度的区别,大家先记住,大O、(Omega)、(Theta)都是表示时间复杂度的3种渐进符号;总的来说 ,大O是小于等于, 是大于等于;是等于。 目录 大O、、表示时间复杂度的区别 渐近分析asymptotic analysis: 上界:big O notation 下界: big Omega notation 代换法 递归树求时间复杂度 归并排序递归树 斐波那契递归树 快速排序递归树 全排列的时间复杂度 主定理 Insertion Sort;Sort A[1,..,n] # 插入排序的伪代码;eg. A= [8,2,4,9,3,6] # 由于第2个元素是2,把2移到8前面:2,8,4,9,3,6; 再看第3个元素4,得到2,4,8,9,3,6,一直循环下去; for j 使得以的常数倍为上界;比如 就表示去掉首项系数2和低阶项之后剩下的小于等于。eg 。 注:这里大O前面的等号不是对称的,我们不能由推出。 eg. 表示的函数集中存在某个函数 ,使得;可看作误差项。 下界: big Omega notation表示存在常数 使得 对所有成立,也就是当n足够大时,有大于等于的某个常数倍; 比如; 也就是渐近地大于 lgn。 【capital theta】是大于等于且小于等于; o 【little o】是严格小于; 【little omega】是严格大于。 求解递归式的方法有3种:代换法【substitution method】;递归树【recursion tree】 代换法先猜测解的形式,再用数学归纳法验证,再求解常数项。也就是求出具体的满足上述定义的 来。 eg已知递归式 , 我们先猜测;也就是假设对所有有; 通过数学归纳【Induction】有 ;要保证余项,所以当时,不等式恒成立。 证明:假设对所有都成立;则 当时才有;所以不成立。 改进Induction hypothesis : 假设对所有有 ; 则;要证明;则余项;所以。也就是当时成立, 是常数,所以要大于;也就是要足够大。 递归树求时间复杂度形如 的递归树可以用后面讲到的主方法、主定理求解。递归思想:是将大问题分解为小问题来求解,然后再将小问题分解为更小的问题。这样一层一层地分解,直到问题规模被分解得足够小,不用继续递归分解为止。这种方法不太严谨;有待证明;通常用递归树找出答案,再用代换法来验证。 归并排序递归树 #归并排序伪代码 merge_sort A[1,...,n] 1. if n =1 ,done, 2. 对A[1,...,ceil(n/2)] 和A[ceil(n/2)+1 ,...,n]递归调用归并排序;其中ceil(n/2)是对n/2取上限 3. 把第2 步得到的两个排序完的表合并。关键在于第3 步的merge,假设有2个排序好的数组 [2,7,13,20] 和[1,9,11,12];由于两个数组都是有序的,所以只需要比较两个数组的第一个元素,找出最小的那个并写到最终的数组中,再把指针向后移一,再比较剩下的两个数组中的元素谁最小;所以先把 1写入到数组中再去掉1 (或者指针后移),由于每次只比较两个元素(和数组元素的数目无关),有【1,2,7,9,11,12,20】所以第3 步的时间为2n for n total elements. 对于归并排序的时间复杂度有: 其中第三步的时间复杂度为;第二部由于把数组从中间位置一分为二再归并,所以为;所以n大于1 的情形,T(n)就等于第2、3步的时间相加。 先来考虑归并排序的这种情形,由于隐式函数和cn都是一阶的,我们用cn代替: ;其中c为大于0 的常数;每次分解都是一分为二,我们把时间上消耗记叙常量O(1). 把它写成递归树,就相当于是对归并排序算法第2、3步的逐步二分 次,直到最后都为叶子节点【时间复杂度为O(1)】。归并排序递归树的构造方法如下图; 现在只需要知道这棵树的高度h,用高度h 乘以每一层的时间消耗n,就可以得到总的时间复杂度O(n*h)。由于归并排序是一棵满二叉树,那h = log2n ,再由于之前讲过的的【对数阶的复杂度可以通过换底公式相互转换,所以用lg表示对数阶】 所以粗略估计的归并排序的时间复杂度就是O(nlogn)。 由上图可以看出,每一层的运行时间都是cn,叶子层的时间为.所以总的运行时间为 .在渐近情况下比要快。所以当输入规模n足够大时,归并排序要优于插入排序。 斐波那契递归树再以一棵斐波那契数列【1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...;它的第n项可写作F(n)=F(n-1)+F(n-2)】的递归树为例,节点的数字表示数据的规模,一个节点的求解可以分解为左右子节点两个问题的求解。 f(n) 分解为f(n - 1) 和 f(n-2),每次数据规模都是-1或者-2,叶子节点的数据规模是1或者2。所以,从根节点到叶子节点,每条路径长度是不一样的。如果每次都是-1,那最长的路径大约是n;如果每次都是 -2,那最短路径大约就是 n/2。每次分解之后的合并操作只需要一次加法运算,我们把这次加法运算的时间消耗记作1; 从上往下,第一层总时间消耗是 1,第二层总时间消耗是 2,第三层的总时间消耗就是4,依次类推,第k+1 层的时间消耗就是2^k。如果路径长度为n,那这个总全就是 2^n -1。 如果路径长度都是 n/2,那整个算法的总时间消耗就是2^(n/2) -1。所以,这个算法的时间复杂度就介于O(2n)和O(2n)/4之间。 快速排序递归树在最好情况下,快速排序每次分区都能一分为二,这个时候用递推公式 T(n) = 2T(n/2) + n,很容易就能推导出时间复杂度是O(nlogn)。假设平均情况下,每次分区之后,两个分区的大小比例为 1:k。当 k =9 时,如果用递推公式的方法来求解时间复杂度的话,递推公式就写成 T(n) = T(n/10) + T(9n/10) + n。把递归分解的过程画成递归树得到下图。 快速排序的每次分区都要遍历待分区区间的所有数据,所以每一层分区操作遍历的数据个数之和就是n。只要求出递归的高度h,就可以得出快排过程的时间复杂度O(hn)。快速排序结束的条件是待排序的小区间大小为1。从根节点n 到叶子节点1,递归树中最短的一个路径是每次都乘以 1/10,最长的路径是每次都乘以9/10。根据复杂度大O表示法,对数复杂度的底数不管是多少,我们统一写成logn,所有当大小比例是1:9时,快速排序的时间复杂度仍然是O(nlogn)。 全排列的时间复杂度全排列问题: 如何把n 个数据( 1,2,3...n)的所有排列都找出来.。如何借助递归树,分析出这个代码的时间复杂度。 /* *假设数组中存储的是 1,2,3...n。 *f(1,2,3...n) = {最后一位是1,f(n - 1)} + {最后一位是2,f(n - 1)} + ...+ {最后一位是n,f(n - 1)} */ public void pringPermutations(int[] data, int n, int k) { // n 表示数组大小,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 tem = data[i]; data[i] = data[k-1]; data[k-1] = tem; pringPermutations(data, n, k-1); tem = data[i]; data[i] = data[k-1]; data[k-1] = tem; } }第一层分解有n次交换操作,第二层有n 个节点,每个节点分解需要 n-1 次交换,所以第二层的交换次数是n*(n-1),同理,第三层交换次数就是n*(n-1)(n-2)。各层交换次数总合就是 n + n(n-1) + n*(n-1)(n-2) +… +n! 。也就是说全排列的递归算法的时间复杂度大于O(n!),小于O(nn!)。 主定理前面我们只是列举了一部分递归树求解时间复杂度的方法,但是更广泛的诀窍是用Master method,它虽然限制很多但是应用超级方便, 它只适用于形如的递归式中:有a个子问题;每个子问题的数据规模是n/b;还要满足, f(n)要是渐近趋正(asympotically positive)的,这类递归树的画法规则为: (1)每个节点的分支数为a; (2) 每层的节点为T(n) = aT(n / b) + f(n)中的f(n)在当前的n/b下的值。 (3)每层的右侧标出当前层中所有节点的和。 下面的主定理给出3种case: case2在算法导论课中又写作 :存在某个 ; 使得 ;则 有下式成立; . 对于case3中 表示下一层的所有值之和。 例题 : 下面的4个递推式的f(n)不同导致的时间复杂度也不同。 【1】 由于 属于case1, , 所以有 【2】 由于 属于case2, , 所以有 【3】 由于 属于case3, , 所以有 【4】 【不适用master method 】则 .
参考资料: 【1】主定理与递归树计算算法时间复杂度 【2】递归树: 如何借助树来求解递归算法的时间复杂度 |
今日新闻 |
推荐新闻 |
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 |