算法设计与分析-递归与分治
更新时间:2023-05-31 02:41:01 阅读量: 实用文档 文档下载
第2章 递归与分治策略
学习要点:
理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。
(1)二分搜索技术;(2)大整数乘法; (3)Strassen矩阵乘法; (4)棋盘覆盖;
(5)合并排序和快速排序;(6)线性时间选择; (7)最接近点对问题; (8)循环赛日程表。
学习如何求解递归式这对于分析递归算法 非常有用,主要有5种方法求解递归式。 1.代换法 2.递归树法 3.主方法 4.生成函数法 5.特征方程根
1.代换法求解递归式1.猜答案(可以不需要知道常数系数确切是 多少,仅需要猜它的形式,如n2 ,再试图 解出它的常数。即先推测递归方程的显式 解) 2.数学归纳法验证递归式。验证是否这个递 归式,按照数学归纳法满足条件。即用数 学归纳法证明推测的正确性。 3.找出常数。
例1:T(n)=4T(n/2)+n; T(1)=1; 1.猜T(n)=O ( n3 );想办法证明T(n)≤c * n 3 2.假设T(k ) ≤c k3 ( k=n/2)即对k满足T(n)=O ( n3 ),即有T(n/2 ) ≤c (n/2)3 T(n)=4T(n/2)+n (对T(n/2)即对k+1看是否满足假设) ≤4c (n/2) 3 +n = c/2* n 3 +n = c * n 3 –(c/2* n 3 – n ) ≤c*n3 (c/2* n 3 – n ≥0,即只要c ≥2就可以) 因此递归式的上界是O ( n3 );
例1:T(n)=4T(n/2)+n; T(1)= θ (1 ); 1.猜T(n)=O ( n2 );根据符号O的定义,对n>n0, 有T(n) ≤ c n2 2.假设T(k ) ≤c k2 ( k<n ) 把这个解代入递归方程,得到 T(n)=4T(n/2)+n ≤4c (n/2) 2 +n = c* n 2 +n = c * n 2 –(–n)而–n不是一个正数,无法得出c * n 2 –(–n) ≤ c * n 2
但假定归纳假设条件为: T(k ) ≤c1k2 -c2 k ( k<n ) 这里减去c2 k ,因其是 低阶项,不会影响到n足够大时的渐近性), 因此T(n)=4T(n/2)+n ≤ 4(c1 (n/2) 2 -c2 (n/2) )+n = c1n2 +n - 2c2 n = c1n2 - c2 n -(c2 n - n) ≤ c1n2 - c2 n (要满足条件 c2 n – n ≥0, 即只要 c2 –1 ≥0,即c2 ≥ 1即可) 即T(k ) ≤c k2 -c k ,对任意的c 1 2 1, c2 ≥ 1成立;
但必须注意c1要足够大,因为: 基本情况T(1) ≤c1 - c2 而T(1)= θ (1 )即T(1)是常数,我们需要选 择c1 ,至少比c2大,而c2 ≥ 1,因此c1要足 够大。 如何求出下界,解决办法之一是假设T(k ) ≥ c1k2 -c2 k ( k<n ),其余步骤类似。
因此递归式的上界是O ( n2 );
练习1:T(n)=4T(n/2)+n; T(1)= θ (1 ); 1.猜T(n)=O ( nlogn );
代换法求解递归式需要先猜出答案大概是 多少,这比较困难。
2.递归树法
递归树法不严谨,但很直观,让你知道答 案大概是多少。一般我们可以用这种方法 求出答案,然后用代换法验证其正确性。
例1:T(n)=2T(n/2)+n; n n/2 n/2 n/4 n/4 n/4 n/4 ……………….. 1 1 1 ….. 11 树的高度是logn,叶节点的个数是n,用递归树求 解递归式就是将每层的复杂度加起来。如第一层 是n,第二层是n/2 + n/2 =n,第三层是n/4 + n/4 + n/4 + n/4 =n…..最后一层(即logn层)是 1+1+…+1=n; 第一层+第二层+第三层+…+最后一层=nlogn。 T(n)=2T(n/2)+n的渐进复杂度是O(nlogn)
例:2:T(n)= T(n/4)+ T(n/2)+n2 即假设有个算法,问题的规模为n,先四等 分地递归,再二等分地递归,再做一个非 递归的n2复杂度的工作。下面用树的形式展 开递归。
T(n)=n2 T(n/4) T(n/2)
=
n2 (n/4)2 (n/2)2
T(n/16) T(n/8) T(n/8) T(n/4)
=
n2 = (n/4)2 (n/2)2
n2 5/16 n2
(n/16) 2 (n/8) 2 (n/8) 2 (n/4) 2 25/256n2 …….. θ (1 ) θ (1 ) ……..θ (1 ) θ (1 )
上述递归树的叶节点是多少个?要注意的是,第 二层表示的意思是将问题规模为n的算法通过递归 将问题规模缩小为n/4+n/2=3n/4; 第三层最左分支表示的意思是将问题规模为n / 4 的算法通过递归将问题规模缩小为 n/16+n/8=3n/16; …… 因此叶节点的个数至少是小于n。
另外,递归树的另一个特点是左分支的分 解速度明显快于右分支,如第二层最左分 支为n / 4,最右分支为n /2;第三层最左分 支为n / 16,最右分支为n /4……因此左分 支递归树的深度要小于右分支的深度。
对各层求和,第一层的和是n2 ,第二层的 和是5/16n2 ((n/4)2 +(n/2)2 ),第三层的和是 52 /162 n2 ((n/16) 2 + (n/8) 2 +(n/8) 2 + (n/4) 2))….可以看出这是一个等比数列,对各层 累加, 即n2 + 5/16n2 +52 /162 n2 +… + 5k/16kn2 +… (1) (1) ≤(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2
等比数列性质: 1+1/2+1/4+1/8+…=2; 因为对二进制而言1+1/2=1.1 1+1/2+1/4=1.11 1+1/2+1/4+1/8+…=1.111…=2; 而(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2中 5/16< ½ 所以(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2 ≤2 n2
故递归式T(n)= T(n/4)+ T(n/2)+n2的上界是 O (n2),下界是Ω (n2) (T(n)= T(n/4)+ T(n/2)+n2 ≥ n2)
递归树法又名递推法T(1)=1 T(n)=2T(n/2)+n2(n≥2) T(n)=2T(n/2)+ n 2 =2(2T(n/2 2)+(n/2) 2 )+ n2 =22T(n/22) +n2/2+ n2 =22(2T(n/23)+(n/22)2)+n2/2+ n2 =23(2T(n/23)+ n2/22+ n2/2+ n2 … =2kT(n/2k)+∑n2/2i (i从0到k-1)
正在阅读:
算法设计与分析-递归与分治05-31
我国居家养老信息化现状分析与路径探究07-01
第四章 交流电路 - 图文03-19
关于党员公开承诺书范文09-08
全国小学生优秀作文选组委会 全国小学生优秀作文选入选 入选作者夏令营报名表09-05
文言文词语和句式之教案303-21
廖彬吉(全) - 浅谈水泥混凝土滑模施工技术(部分摘抄)06-23
观赏树木学讲义02-26
家乡的小溪作文350字06-27
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 递归
- 分治
- 算法
- 分析
- 设计
- 投资大师查理 芒格的名言
- 海洋水的运动----世界洋流
- 项目经理_施工员_质检员_安全员_岗位职责
- 褥垫层对刚性桩复合地基工作特性影响的数值分析
- 表彰大会流程及主持词
- 地质罗盘的使用方法
- 万科物业安全管理工作程序
- 冰箱新产品设计开发流程DOC.doc
- 2014年滨州继续医学教育公共课答案
- 大学语文2013笔记
- 江苏省盱眙县黄花塘初级中学七年级英语上册 Unit 6 Food and lifestyle(第6课时)教案 (新版)牛津版
- 钢结构设计指导书
- 秦许学区2011-2012学年第二学期工作计划
- 铁磁_反铁磁双层膜中交换偏置
- TRR-1全数字软起动板产品说明书简化版
- 基于MATLAB的骨架提取算法的研究实现
- 成本管理会计练习题第2章带答案
- “我的班级我的团”团支部目标成长计划实施意见
- 塑料旋钮模具设计
- 2015届最新国家和国际组织试题汇编