算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法

算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法

在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n),本文针对形如T(n)=aT(n/b)+f(n)的递归方程进行讨论,以期望找出通用的递归方程的求解方式。

算法设计教材中给出的Master定理可以解决该类方程的绝大多数情况,根据Master定理:o-渐进上界、w-渐进下界、O-渐进确界。

设a≥1,b>1为常数,f(n)为函数,T(n)=aT(n/b)+f(n)为非负数,令x=logba:

1. f(n)=o(nx-e),e>0,那么T(n)=O(nx)。

2. f(n)=O(nx),那么T(n)=O(nx logn)。

3. f(n)=w(nx+e),e>0且对于某个常数c<1和所有充分大的n有af(n/b)≤cf(n),那么T(n)=O(f(n))。

然而,Master定理并没有完全包括所有的f(n)的情况。注意到条件1和3中的e总是大于0的,所以在条件1和2、条件2和3之间存在所谓的“间隙”,使得某些f(n)在该情况下不能使用该定理。因此,我们需要找到在Master定理不能使用的情况下如何解递归方程的比较通用的办法——递归树。

经过分析,递归树解法包含了Master定理,但是Master定理可以方便的判断出递归方程的解。产生这种结果的原因关键在于f(n)的形式,显然,当f(n)是n的多项式p(n)形式的话必然满足Master定理的要求,但是f(n)不是多项式就需要另当别论了。

下面就题目所列出的递归方程形式进行分析。

、f(n)是n的多项式p(n)=f(n)

因为f(n)是多项式,设p(n)=O(nk),k≥0。根据递归树计算方式,有:

T(n)= aT(n/b)+nk 。

T(n/b)= aT(n/b2)+(n/b)k 。

T((n/b2)= aT(n/b3)+( n/b2)k 。

……

于是得到:T(n)= nk (1+ a/ bk + (a/ bk)2 + (a/ bk)3 +···+ (a/ bk)h),h=logbn。

1:logba=k

这种情况下a/ bk= 1,显然T(n)= O(nk logbn)。

2:logba≠k

此时等比数列公比不是1,根据等比数列求和公式化简得到:

T(n)=( nk –nx)/(1-a/bk),x=logba。

如果logba<k,则T(n)= O(nk)。

如果logba>k,则T(n)= O(nx)。x=logba。

通过以上的计算表明,在Master定理的条件中,针对f(n)为多项式的情况可以使用递归树的方法进行证明和计算。同样,在f(n)不是多项式的时候也可以通过的这种方式得到方程的解。

、f(n)是一般函数

当f(n)不是n的多项式的时候,计算就会变得比较复杂,有时可能会也找不到最终的解。但是递归树的方法给我们一种更好使用的解决办法。下面根据一个简单的例子说明这一点:

当a=b=2、f(n)=nlgn时候(lgn:log2n的简记),计算递归方程的解。

T(n)= 2T(n/2)+nlgn 。

T(n/b)= 2T(n/22)+(n/2)lg(n/2)。

T((n/b2)= 2T(n/23)+ (n/22)lg(n/22)。

……

于是得到:T(n)= nlgn+(nlgn-lg2)+ (nlgn-2lg2)+ (nlgn-22lg2)+···+(nlgn-2hlg2),h=lgn。

根据等差、等比数列求和公式化简有:

T(n)=n(lgn)2 –(n-1)lg2,所以T(n)= O( n(lgn)2),而不是O( nlgn)。

通过这个例子可以看出,当f(n)不是多项式的时候计算就有可能变得比较复杂,甚至无法计算。但是通过Master定理以及具体的数学变换技巧在某些情况下还是可行的。

综上所述,可以得出以下结论:在针对形如T(n)=aT(n/b)+f(n)的递归方程求解方法里,使用递归树是一种比较可行的通用办法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏随笔小哥哥

程序员必须知道的10大基础实用算法及其讲解:排序、查找、搜索和分类等

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

7300
来自专栏大数据风控

R中如何用ifelse进行数据分组

数据分组,根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间部分来研究,以揭示内在的联系和规律性; 在R中,我们常用ifelse函数来进...

36180
来自专栏钱塘大数据

【干货】十大必须掌握的基础实用算法及其讲解

作者:CSDN大数据 算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下...

28860
来自专栏游戏开发那些事

【随笔】游戏程序开发必知的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n logn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事...

10530
来自专栏程序员互动联盟

程序员必须要掌握的十大经典算法

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

445130
来自专栏华章科技

程序员必须知道的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,...

12020
来自专栏智能算法

程序员必须知道的十大基础实用算法及其讲解

出自博客园 原文地址:http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法...

39080
来自专栏CSDN技术头条

程序员必须知道的十大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

21450
来自专栏潇涧技术专栏

Problem: Delete Number Problem

这题可以使用贪心策略,每次从高位向低位数,删除高位比低位数字小的那位上的数字,直到删除了k位之后,得到的数字肯定是最大值。

9620
来自专栏小樱的经验随笔

Codeforces 626E Simple Skewness(暴力枚举+二分)

E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

31740

扫码关注云+社区

领取腾讯云代金券