提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、代换法
- 二、递归树法
- 三.主方法
- 总结
前言
学无止境,笔勤不辍。很久没有更新算法专栏了…笔者终于找到时间来更新了。今天,笔者给大家分享一下三种求解递归式的时间复杂度的方法,希望能与大家一起学习进步!!!
简单补充一下 递归式的定义,递归式由两部分组成:1.结束条件 2.递归体
这个递归式的解是 T(n) = O(N *lg N)
一、代换法
先猜测有某个界存在,然后利用数学归纳法,证明猜想的正确性。
步骤:
1.猜测解的形式
2.用数学归纳法找出能让这个时间复杂度解有效的常数
下面给一个例子:
求T(n)=2T(⌊n/2⌋)+n 的时间复杂度
猜其解为T (n) = O(n lg n)
存在常数c使得T (n) ≤ cn lg n
假设⌊n/2⌋时式子成立,即 T(⌊n/2⌋)≤ c ⌊n/2⌋lg(⌊n/2⌋成立
此时,T(n)≤ 2(c ⌊n/2⌋lg(⌊n/2⌋)) + n
≤ cn lg(n/2) + n
=cn lg n - cn lg 2 + n
=cn lg n - cn + n
≤ cn lg n
当1≤ c时,最后一步成立,即证明成功
这里的lg是以2为底的
`不过这里要考虑一下边界条件,n>=2的时候是成立的,但是n=1时,是有问题的 因为 T(1)=1 but cn lg 1 = 0`
这里证明时,可能会遇到:是同一数量级,但是有低阶项多出,方法是:证明猜想时,减去一个低阶项。
二、递归树法
将递归式转换成树形结构,树中的节点代表在不同递归层次付出的代价,最后利用对和式限界的技术来解出递归式(最终求和求解)
递归树是一种得到好猜测的直接方法
通常可以容忍小量的不良量
给出例子:
求解 T (n) = 3T (⌊n/4⌋) + Θ(n2)
值得注意的是,该树的所有结点的和是T(n)
之后的证明运用代换法(数学归纳法)
递归树法是用来找寻一个近似的合适解的方法
三.主方法
给出递归形式T(n)=aT(n/b)+f(n)的界,其中a≥1,b>1,f(n)是给定的函数。通过定义求解递归式的可靠猜测解
设a ≥ 1 和 b > 1 是常数,设 f (n) 为一函数
T(n) = aT(n/b) + f(n)有这种形式
对非负整数,其中 n/b 指⌊n/b⌋ 或 ⌈n/b⌉。那么 T (n)
可能有如下的渐近界(近似解)
给出例子:
T (n) = T (2n/3) + 1
a = 1, b = 3/2, f (n) = 1
适合第二种情况,所以T(n) = Θ(lg n)
之后的证明运用代换法(数学归纳法)
总结
以上就是今天要讲的内容,本文粗略介绍了三种求递归式时间复杂度的方法,后续笔者会更改精修。今天的内容就分享到这里了,希望能给大家一些帮助,教室要关门了,笔者再不走就要被关起来了,后续笔者也会定期更新内容,坚持学习… 再重复一遍口号:学无止境,笔勤不辍!