第一章算法与设计

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级网络,*,计算机算法设计与分析,韩丽霞,1,参考书目：,王红梅，算法设计与分析，清华大学出版社，,2006,。,吕国英，算法设计与分析，清华大学出版社，,2009,。,Alfred V.,Aho,等，（黄林鹏等译）计算机算法的设计与分析，机械工业出版社，,2007,。,R.C.T.Lee,，（王卫东译）算法设计与分析导引，机械工业出版社，,2007,。,2,内容安排：,一 算法概述,二 递归与分治策略,(I),三 动态规划,(I,H),四 贪心算法,(I),五 回溯法,(H),六 分支限界法,(H),七 随机化算法,3,第一章 算法概述,Algorithm Introduction,4,学习要求：,理解算法的概念,理解什么是程序，程序与算法的区别和内在联系,掌握算法计算复杂性的概念,掌握算法渐进复杂性的数学表达,掌握用,C+,语言描述算法的方法,5,1.1,算法与程序,1,、算法,一系列将问题的输入转换为输出的计算,或操作步骤。,6,2.,算法的性质,输入：有外部提供的量作为算法的输入。,输出：算法产生至少一个量作为输出。,确定性：组成算法的每条指令是清晰、无歧义的。,有限性：算法中每条指令的执行次数是有限的，,执行每条指令的时间也是有限的。,7,3,、程序与算法的区别与内在联系,程序是算法用某种程序设计语言的具体实现。,程序可以不满足算法的性质,(4),。,4,、算法描述语言,自然语言、,流程图、,程序设计语言、,伪代码等。,8,理解问题,算法分析,设计程序,5,、问题求解,(Problem Solving),证明正确性,数学模型,设计算法,9,1.2,算法复杂性分析,算法的复杂性,(C):,算法执行所需的时间和空间的数量。,1,、复杂性的计量,算法的复杂性,(C),时间复杂性,(T),空间复杂性,(S),10,问题的规模,算法,输入,11,时间复杂性：,元运算时间,元运算种类,元运算次数,？,12,(P5 1-4),例 题,1-1,13,最坏情况：,最好情况：,14,平均情况：,输入,I,的概率,15,例 题,1-2,n,Int,Find(int,A,int,n),i:=0;a,while in t,i:=i+1;(a+s),If,Ai,=k t,Break,Reture,i a,分析,:,问题的规模为,n,设元运算执行时间为赋值,:a,判断,:t,加法,:s,。,16,2,、复杂性的渐进性态,1),渐进性态,17,*渐进分析,适用于,N,充分大的情况,当问题的规模很小时,或比较的两算法,同阶时,则不能做这种简化,.,18,2,）渐进性态的阶,(1),大,O,表示法,(,算法运行时间的上限,),19,20,21,?,*上界的阶越低，结果就越有价值。,22,23,估计二重循环算法在最坏情况下时间复杂性的阶。,for i:=1 to N do,for j:=1 to i do,s1,s2,s3,s4;s1,s2,s3,s4,为单一赋值语句,例 题,1-4,分析：内循环体只需要,O(1),时间，故,24,(2),大,表示法,(,算法运行时间的下限）,25,(3),表示法,26,指数级,阶乘级,常数级,对数级,线性级,多项式级,27,a),对问题处理能力、运行时间有影响的因素有：,硬件设备的性能,系统软件,输入数据,b),起决定性作用的是算法渐近复杂度。,c),在问题规模较小时，常数因子也不可忽视。,d),实际工作中考虑的因素,4,算法复杂度的影响,28,练习：,例,1,：解决某问题有三种算法，复杂性分别为,1000N,、,10N,2,、,2,N,，在一台机器上可处理问题的规模分别为,S1,、,S2,、,S3,。,若机器速度提高到原来的,10,倍，问在同样时间内可处理问题的大小如何？,解：,复杂性 原来处理问题规模 速度提高以后,1000N S1 10S1,10N2 S2 3.16S2,2N S3,S3,+log10S3+3.32,29,例,2,：,问题,P,的算法复杂度为,T(n)=n,3,（,毫秒），现改善为,T(n)=n,2,（,毫秒）。问原来运行一小时的问题实例，现在要运行多少时间？,解,：,设实例大小为,n,，,则,n,3,=,3600*1000,n=,153.3,现在需要时间,t=153.3,2,毫秒,23.5,秒,30,总结,:,算法的概念。,程序、算法,算法的空间复杂度和时间复杂度。,大,O,表示法、大,表示法、,表示法,。,31,