算法课件全121301ADA09减治法减常因子算法I
25页1、Decrease and Conquer (I),Chapter 5,Introduction to Decrease-and-Conquer Decrease-by-a-Constant-Factor Algorithms The Binary Search Fake-coin Problem Russian Peasant Multiplication Josephus Problem,2019/6/21,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should Master the basic idea and all kinds of variations of decrease and conquer technique Master the binary search algorithm and its best-case, worst-case and average-case analysis Under
2、stand the fake coin problem and its solution Be familiar with the Russian peasant multiplication method Understand the josephus problem and its solution,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Decrease-and-Conquer (basic idea),Reduce problem instance to smaller instance of the same problem Solve smaller instance Extend solution of smaller instance to obtain solution to original instance,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,3 Types of Decrease and
3、Conquer,Decrease by a constant (usually by 1) Insertion sort Graph traversal algorithms (DFS and BFS) Algorithms for generating permutations, subsets Decrease by a constant factor (usually by half) Binary search Fake-coin problem Russian peasant multiplication Josephus problem Variable-size decrease Euclids algorithm The kth smallest element find algorithm Interpolation search,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Whats the difference? (example),Brute Force:,Consider the
4、 problem of exponentiation: an,Divide and conquer:,Decrease by one:,Decrease by constant factor:,The Application of Decrease by a constant factor technique,Search problem The binary search (S4.3, P135-139) Numerical problem Russian peasant multiplication (S5.5) Combinatorial problem Fake-coin problem (S5.5) Josephus problem (S5.5),2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Binary Search (basic idea),If the key is larger than the middle element, the key must be in the second h
《算法课件全121301ADA09减治法减常因子算法I》由会员E****分享,可在线阅读,更多相关《算法课件全121301ADA09减治法减常因子算法I》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-05-03 27页
2024-05-03 28页
2024-05-03 28页
2024-05-03 34页
2024-05-03 33页
2024-05-03 29页
2024-05-03 31页
2024-05-03 27页
2024-05-03 27页
2024-05-03 33页