算法设计与分析40学时课件ch2new
39页1、第二章 数学基础,骆吉洲 计算机科学与工程系,2.1 计算复杂性函数的阶 2.2 递归方程,提要,2.1.1 同阶函数集合 2.1.2 低阶函数集合 2.1.3 高阶函数集合 2.1.4 严格低阶函数集合 2.1.5 严格高阶函数集合 2.1.6 函数阶的性质,2.1 计算复杂性函数的阶,2.1.1 同阶函数集合,定义2.1.1 (同阶函数集合) (f(n)=g(n) | c1, c20, n0, nn0, c1f(n)g(n) c2f(n) 称为与f(n) 同阶的函数集合。,Example,例2 证明,证. 如果存在c1、c2 0,n0使得当nn0 时,c16n3c2 n2 。于是,当nc2 /6时, n c2 /6,矛盾。,Example,Example,2.1.2 低阶函数集合,Example,例 2 证明 n=O(n2).,2.1.3 高阶函数集合,2.1.4 严格低阶函数集合,2.1.5 严格高阶函数集合,Example,例 2. 证明 n2/2 w(n2),2.1.6 函数阶的性质,2.1.6 函数阶的性质(续),注意,!,递归方程: 递归方程是使用小的输入值来描述 一个函
2、数的方程或不等式.,2.2 递归方程,递归方程例: Merge-sort排序算法的复杂性方程 T(n)=(1) if n=1 T(n)=2T(n/2)+(n) if n1. T(n)的解是(nlogn),迭代方法: 把方程转化为一个和式 然后用估计和的方法来求解. 替换方法: 先猜测方程的解, 然后用数学归纳法证明. Master方法: 求解型为T(n)=aT(n/b)+f(n)的递归方程,求解递归方程的三个主要方法,方法: 循环地展开递归方程, 把递归方程转化为和式, 然后可使用求和技术解之,2.2.1 迭代方法, DB-LAB (2003),例2.T(n)=2T(n/2)+cn,=22T(n/22)+cn+cn,=23T(n/23)+cn+cn+cn =,=2kT(n/2k)+knc,=2kT(1)+knc n=2k,=nT(1)+cn log n =(nlogn),方法: 1.变量代换,将方程转换成已知方程 2.先根据方程的形式猜测解 然后用数学归纳法证明,2.2.2 替换法,例1.T(n)=2T(n/2+17)+n,变量代换,令n=m+34,则,S(m)=2S(m/2)+m+34,令T(m+34)=S(m),则,T(m+34)=2T(m/2+34)+m+34,S(m)=(mlogm),T(n)=(nlogn),例2.T(n)=2T(n1/2)+logn,令n=2m,则,S(m)=2S(m/2)+m,令T(2m)=S(m),则,T(2m)=2T(2m/2)+m,S(m)=(mlogm),T(n)=(logn loglogn),例1.T(n)=2T(n/2+17)+n,先猜后证,令n=m+34,则,S(m)=2S(m/2)+m+34,令T(m+34)=S(m),则,T(m+34)=2T(m/2+34)+m+34,S(m)=(mlogm),T(n)=(nlogn),猜测方法: 猜测上下界,减少不确定性范围,细微差别的处理,问题:猜测正确,数学归纳法的归纳步 似乎证不出来 解决方法:从猜测结论中减去一个低阶项, 可能方法就能用了, DB-LAB (2003),避免陷阱,2.2.3 Master method,Master 定理,C1,对于红色部分,Master定理无能为力,Master定理的使用,Master定理的使用(续),
《算法设计与分析40学时课件ch2new》由会员E****分享,可在线阅读,更多相关《算法设计与分析40学时课件ch2new》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页