算法课件全121301ADA03算法分析基础-递归与非递归算法的分析方法
25页1、2019/6/21,2,2012-2013-01Design and Analysis of Algorithm SCUN,Review of last class,Methods for describing algorithm The framework for analyzing the time efficiency of an algorithm The best-case, worst-case and average-case analysis Rate of growth and two asymptotic notations , O,Fundamentals of the Analysis of Algorithm Efficiency (II),Chapter 2,1、 Formal definition of asymptotic notations 2、 Mathematical Background 3、 Analysis of non-recursive algorithms,2019/6/21,4,2012-2013-01Design and Analy
2、sis of Algorithm SCUN,Goals of this lecture,At the end of this lecture, you should Master asymptotic notations Be familial with the basic mathematical tools Master the analysis of non-recursive algorithms,2019/6/21,5,2012-2013-01Design and Analysis of Algorithm SCUN,Asymptotic Notation: ,-notation: Call f(n) = (g(n) if there exist positive constants c1, c2, and n0 such that 0 c1g(n) f(n) c2g(n) for all n n0. f(n) = 2n3+3n-5 = (n3) f(n) = 2n4+1 = (n3) ?,2019/6/21,6,2012-2013-01Design and Analysis
3、 of Algorithm SCUN,Asymptotic Notation: ,f(n) = (g(n),n,f(n),c2g(n),n0,c1g(n),2019/6/21,7,2012-2013-01Design and Analysis of Algorithm SCUN,Using Limits for Comparing Orders of Growth,A much more convenient method for comparing the orders of growth of two specific functions is based on computing the limit of the ratio of two functions:,The first two cases, say , mean that f(n) O(g(n),The last two cases, say , mean that f(n) (g(n),The second cases, say , mean that f(n) (g(n),Compare the orders of
4、 growth of logn and,Compare the orders of growth of n! and 2n,Compare the orders of growth of 1/2n(n-1) and n2,2019/6/21,8,2012-2013-01Design and Analysis of Algorithm SCUN,Orders of growth of some important functions,All logarithmic functions loga n belong to the same class (log n) no matter what the logarithms base a 1 is All polynomials of the same degree k belong to the same class: aknk + ak-1nk-1 + + a0 (nk) Exponential functions an have different orders of growth for different as,2019/6/21
《算法课件全121301ADA03算法分析基础-递归与非递归算法的分析方法》由会员E****分享,可在线阅读,更多相关《算法课件全121301ADA03算法分析基础-递归与非递归算法的分析方法》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页