算法复杂性分析算法概述
70页1、算法概述,杨秋妹 ,程序=数据结构+算法,乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离,如何找出这一最短行程?,建立解题模型数据结构 解决方法,什么是算法,算法是一个有穷的解决问题的指令序列。每条指令都必须有清楚的含义并且在有穷长的时间内用有穷的动作完成。 一个算法无论接受任何输入,都必须在有穷步内停止。,排序问题,输入:由n个数构成的一个序列 输出:对输入序列的一个排列(重排),使得a1=a2=an 算法:插入排序,冒泡排序,快速排序,合并排序等,算法的几个特性,算法是指解决问题的一种方法或一个过程。 满足性质: (1)输入:有零个或多个外部提供的量作为算法的输入。 (2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法的每条指令是清晰,无歧义的。 (4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。,什么是程序,程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有穷性,算法的描述,自然语言; 程序设计语言; 类程序语言,算法可以解决的问题,人类基因的目标是找出人类DNA的所有十万种
2、基因,确定构成人类DNA的30亿种化学基对的各种序列,将这些信息存储在数据库中,并开发出用于进行这方面数据分析的工具。 因特网快速地访问和检索大量的信息,电子商务保持信用卡号、密码、银行结单等信息的私密性,公共密钥加密技术和数字签名技术 制造业和其他商业应用中,是否能最有效地分配稀有资源,例如,石油公司确定在何处打井,以求最大化预期效益;美国总统候选人希望确定该把宣传的资金花在何处,以求赢得竞选的可能性最大;,常用的算法设计方法,递归法(Recursion) 分治法(Divide-and Conquer)、 贪心法(Greedy) 动态规划(Dynamic Programming)、 回溯(Backtracking) 分支限界法(Branch and Bound) 近似算法(Approximation),问题求解,理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,算法的设计目标,算法应易于理解、编程和调试 算法应尽可能有效地利用计算机的资源,特别地,应尽可能快地运行,好算法的判断标准,1.正确性 2.健壮性 3.时间复杂性 4.空间复杂性 5.可读性 6. 灵活性(Fle
3、xibility)、可重用性(Reuseabale)等,算法复杂度分析,算法复杂性,体现在运行该算法所需要的计算机资源多少上 所需资源越多,该算法的复杂性越高 所需资源越少,该算法的复杂性越低,时间复杂性:算法执行需要的时间资源 空间复杂性:算法执行需要的空间资源,百鸡问题,公元5世纪末,我国古代数学家张丘建在他所撰写的算经中,提出了这样的一个问题:“鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一。百钱买百鸡,问鸡翁、母、雏各几何?”,a:公鸡数 b:母鸡数 c:小鸡数 a + b + c = 100 5a + 3b + c/3 = 100 c % 3 = 0,void chicken_question(int n, int ,算法有三重循环 内循环体的执行次数为(n+1)(n+1)(n+1),void chicken_problem(int n, int ,算法有两重循环 内循环体执行次数为(n/5 + 1)(n/3 + 1),货郎担问题,货郎担问题是一个经典问题。某售货员要到若干个城市销售货物,已知各城市之间的距离,要求售货员选择出发的城市及旅行路线,使每一个城市仅经过一次,最后回
4、到原出发城市,而总路程最短。,用图的顶点代表城市,边的权重表示城市间的距离,这个问题可以转化为求一个图的最短哈密顿回路,哈密顿回路可以定义为n1个相邻节点vi0,vin-1,vi0的一个序列 可以通过生成n1个中间城市的组合来得到所有的旅行路线,计算这些路线的长度,然后求得最短的线路,算法时间复杂度 O(n!),对于所设计的算法,如何说明它是有效的? 如果对于同一问题,有多个不同的解法,如何知道哪一个算法更有效? 算法复杂性分析目的在于选择合适的算法和改进算法,实验测量法(实际执行时间、执行指令的条数) 把算法用某种程序设计语言实现并在计算机上运行,计算实际运行时间,如何进行算法时间效率分析,例:让一台更快的、运行插入排序的计算机(计算机A)与一台较慢的、运行合并排序的计算机(计算机B)进行比较。两者都要对一个大小为一百万个数的数组进行排序。假设计算机A每秒能执行10亿条指令,而计算机B每秒只能执行一千万条指令。,计算机A花费的时间: 2*(106)2条指令/109条指令/秒2000秒 计算机B花费的时间: 50*106lg106条指令/107条指令/秒100秒,影响实验测量时间的因素
《算法复杂性分析算法概述》由会员E****分享,可在线阅读,更多相关《算法复杂性分析算法概述》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课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页