算法课件2015第1.5章
15页1.5章 递归方程的渐进性,马志强,递归方程的渐进性,合并排序的复杂性,解决方法,Substitution方法(替代法): Guess first, 然后用数学归纳法证明. Recursion-tree方法(递归树): 把递归方程用树的形式展开 然后用估计和的方法来求解. Master方法: 求解型为T(n)=aT(n/b)+f(n)的递归方程,Substitution方法,猜测 ,也就是 当n=1时, 不成立 当n=2时, 当c2是成立 假设结论对于n/2成立,即,当c1时,Substitution方法,How to guess T(n)?,Recursion-tree方法,以树的形式循环地展开递归方程 把递归方程转化为和式 然后可使用求和技术解之,Recursion-tree方法,假设对于n/4有,当c 时,Master方法,Master方法,(3)若 , 是常数,且对于某个常数c1和所有充分大的n有 ,则,(2) 若 , 则,Master方法,Master方法,对于红色部分,Master定理无能为力,但不存在0,使得,f (n) 大于 ,但不多项式大于 ,Master定理不适用,
《算法课件2015第1.5章》由会员E****分享,可在线阅读,更多相关《算法课件2015第1.5章》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课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页