在前面的文章中,我们讨论了循环的时间复杂度分析。很多算法是具有递归性质的,当我们的分析的时候得到的是递推关系的时间复杂度。
例如,在归并排序中,对一个给定的数组进行排序,我们把它分成两半,并对这两半递归地重复这个过程。最后,我们合并结果。时间复杂度可以写成:
T(n) = 2T(n/2) + cn. 还有许多其他算法,如二分查找,汉诺塔等都可以递推公式。
主要有三种方式来递归公式。
1)替代法:我们做一个猜测的解,然后用数学归纳法证明的猜测是正确的或不正确的。
例如:T(n) = 2T(n/2) + n。 我们猜测解为:T(n) = O(nLogn).
现在用数学归纳法来证明我们的猜测。
需要证明 T(n) <= cn Logn. 我们可以假设对于值小于n时这个公式是成立的。
1 |
T(n) = 2T(n/2) + n |
2 |
<= cn/2Log(n/2) + n
|
3 |
= cnLogn - cnLog2 + n
|
4 |
= cnLogn - cn + n
|
5 |
<= cnLogn
|
2)递归树方法
在这个方法中,我们得出一个递归调用树,并计算树的每一层的时间。最后,我们对各层相加。要绘制递归树,我们从给定的递归出发,一直递推下去直到我们找到里面的模式。这个模式一般是典型的等差或等比级数。
例如对这个递归方程:T(n) = T(n/4) + T(n/2) + cn^2
1 |
cn2 (cn2 即为 cn^2)
|
2 |
/ \
|
3 |
T(n/4) T(n/2) |
如果我们进一步分解表达T(n / 4)和T(n / 2), 我们得到以下递归树。
01 |
cn2
|
02 |
/ \
|
03 |
c(n2)/16 c(n2)/4
|
04 |
/ \ / \
|
05 |
T(n/16) T(n/8) T(n/8) T(n/4)
|
06 |
(一直向下分解cn2)
|
07 |
/ \
|
08 |
c(n2)/16 c(n2)/4
|
09 |
/ \ / \
|
10 |
c(n2)/256 c(n2)/64 c(n2)/64 c(n2)/16 |
11 |
/ \ / \ / \ / \
|
要知道 T(n)的值,我们需要相加所有层的值。如果从最上面开始加,可以得到下面的式子:
T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….
上述系列是几何级数为5/16。
为得到一个上限,我们求无穷级数的和: (n^2)/(1 – 5/16) 即为 O(n^2)
主定理
主定理是解决递归的一种直接方法。但仅用于一些类型或可以转换为以下类型的递归公式:
T(n) = aT(n/b) + f(n) (a >= 1 且 b > 1)
有以下三种情况:
如何计算?
主定理主要来自递归树方法。如果我们画T(n) 的递归树 T(n) = aT(n/b) + f(n),我们会发现 根节点的值为f(n) ,所有的叶子节点的和为 其中 c为 .
递归树的高度为:
在递归树的方法中,我们计算所有节点的和。如果在叶子节点的值是多项式的,那么叶子是占主导地位的一部分,而我们的结果变成叶子节点的值(情况1)。
如果叶和根是渐近一样的,那么结果就变成高度乘以在所有层的和(情况2)。如果根节点的值是渐近多,那么我们的结果变成在根的值(情况3)
一些时间复杂度可以使用主定理进行评估的例子
归并排序:为T(n) = 2T(n/2) + 。它属于在第二种情况, c为1并且 也1。因此该解决方案是
二分查找:T(n) = T(n/2) + . 。它也属于情况2. c是0并且也为0。因此该解决方案是
注:
1)主定理并不能用来解决所有形式为 T(n) = aT(n/b) + f(n) 的递归式,往往和给定的3种情况有第一定的差距。例如 T(n) = 2T(n/2) + n/Logn 不能用主定理解决。
2) 第二种情况可以扩展为 f(n) = . 如果 k >= 0 且 c = , 那么 T(n) =
参考:http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/
参考视频地址:http://v.163.com/movie/2010/12/2/E/M6UTT5U0I_M6V2T4T2E.html
相关推荐
关于递归算法时间复杂度分析的探讨.pdf
对算法进行时间复杂度分析是算法分析与研究 的重要内 容, 而对递 归算法分 析其时间 复杂度时 往往比较 困难. 提出了用组合数学中的母函数与递推关系理论来分析一些特 殊的递归算法的 时间复杂度, 并 同时得出三个 ...
算法时间复杂度分析中递归方程求解方法综述
用递推关系理论分析递归算法的时间复杂度.doc
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
递归算法与循环算法的分析
用非递归解决八皇后的问题,是经典的非递归算法,学习数据结构中很有用
最好情况下, 最坏情况下, 平均情况下的时间复杂度
01-001数据结构的概念和基本术语、...10-002堆排序、多关键字的排序、基数排序、排序时间复杂度的分析 10-003外部排序的基本过程、索引文件、哈希文件的结构 10-004多关键字文件的特点、倒排文件、判定树、二叉平衡树
- 算法复杂度分析 - 算法思维 - 分治 - 贪心 - 动态规划 - 高级数据结构 - 树、图 - 深度优先和广度优先搜索 本小节会带领大家快速过一遍数据结构和算法,重点讲解一些常考、前端会用到的算法和数据结构。 --...
2、递归算法通用解决思路 3、实战演练(从初级到高阶) 4、递归函数调用栈 5、递归算法时间复杂度分析与求解 力争让大家对递归的认知能上一个新台阶,特别会对递归的精华:时间复杂度作详细剖析,会给大家总结...
用伪代码或程序语言写出二分搜索的算法,并分析其时间复杂度。 简述分治法在每一层递归上的三个步骤的具体内容。 简述快速排序的具体过程。 有面值分别为1、5和11单位的硬币,希望找回总额为15单位的硬币,贪心算法...
我们在第 12 节《排序(下)》那里讲过,如何利用递推公式,求解归并排序、快速排序的时间复杂度,但是,有些情况,比如快排的平均时间复杂度的分析,用递推公式的话,
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
算法设计与分析-4动态规划金罐游戏.pptx 蛮力法(简单重复递归)和动态规划解决金罐问题 状态数组 子问题 状态方程 蛮力法(时间复杂度O(2n))和动态规划(时间复杂度O(n2)) 空间效率 当前序列相对最大金币值 通过...
快速排序的分治思想 时间复杂度分析 数学归纳法 Karatsuba快速乘法 Strassen矩阵乘法
递归算法的时间复杂度 2-6 均摊时间复杂度分析(Amortized Time Analysis) 2-7 避免复杂度的震荡 第三章:数组中的问题其实最常见 3-1 从二分查找法看如何写出正确的程序 3-2 改变变量定义,依然可以写出正确的算法...
算法分析与设计 课程作业 完整版。 包含第二章——递归算法 1.汉诺塔问题 2.斐波纳契数列 3.八皇后问题 第三章——分治算法 1.归并排序 2.快速排序 3.折半查找 4.选择问题 5.最大子段 第四章——贪心算法 1.背包问题...
插入排序算法、归并排序算法的c++实现,以及递归算法的复杂性分析文档。详情可以参考我的博客,http://blog.csdn.net/zhongkelee