《第八章算法基础.ppt》由会员分享，可在线阅读，更多相关《第八章算法基础.ppt（65页珍藏版）》请在三一办公上搜索。
1、第八章 算法基础,西北工业大学应用数学系聂玉峰,算法概念,数学建模竞赛的过程算法的概念算法的分类算法的评价,1.1 建模竞赛的过程,实际上是命题人（某个领域的专家）提出实际问题参赛人首先读题，分析问题，依照自己的理解准确阐述问题；辨析问题中的主要矛盾和次要矛盾，并在合理假设的条件下，运用各种数学理论、工具和方法，建立起问题中不同量之间的约束关系，进而得到完备的数学模型；在研究模型解的存在性与惟一性如何求其解 利用解对模型的正确性进行评价。,1.2 算法的概念,当数学模型的分析解得不到时，使用计算机进行求解。我们不会做的计算机肯定不会做，只有当我们会做，但因为数据计算量太大时，把自己的求解过程（
2、算法）编写成程序，计算机将其编译、运行得到计算结果。所谓（串行）算法就是求解一个问题类的无二义性的有穷过程，这里过程明确无歧义的描述由有限操作（算术运算、逻辑运算、字符运算、读写操作等）及有限操作对象合成的按一定顺序执行的有限序列。原始的可以变化的有限操作对象就是有限输入数据，它所有可能允许的变化构成求解的问题类。,1.3 算法的分类,对给定的输入数据，算法运行后得到的数据结果也是有限的，这样可以把算法看成有限输入数据和有限输出结果之间的对应关系。将以浮点算术运算为主的算法称为数值型算法，如线性方程组的求解，数值积分的计算，微分方程初边值问题的求解等。其它算法称为非数值型算法，如排序问题，匹配
3、查找问题等。,1.4 算法的评价,算法在保证可靠的大前提下再评价其优劣才是有价值的。数值型算法的可靠性算法的收敛性、稳定性、误差估计等算法必须在有限的时间内得到计算结果，如果某问题类的一个求解过程是无限长，需要将其截断得到求解算法，并产生截断误差。算法的收敛性就是研究当运行时间趋于无限长时，算法的解是否趋于真实解，即截断误差是否趋于零。非数值型算法的可靠性更为强调对于整体问题类算法计算结果的正确性。,算法的评价（2）,评价一个可靠算法的优劣，应该考虑其时间复杂度（计算机运行时间）、空间复杂度（占据计算机存储空间的多少）以及逻辑复杂度（影响程序开发的周期以及维护）。,2数值型算法的收敛阶,迭代是
4、构造数值问题算法的基本思想之一，迭代的结果是得到问题解的一个近似序列.如果对于问题类中任一问题，迭代次数k趋于无穷大时序列极限存在，并且就是该问题的准确解，则称该迭代算法收敛到问题的解。,2.1 数列收敛阶的定义,2.2 举例,2.3 2阶收敛举例,2.4 算法的收敛阶,类似地，如果收敛的数列是由迭代算法产生的，定义数列的收敛阶为算法的收敛阶。不过需要注意，算法是对问题类的算法，不是针对一个特定问题的，这样算法的收敛阶应该是由该算法生成的序列都具有的共同特征。,2.5 时间花费与收敛速度,对于不同的算法，若每一迭代步的时间花费相当，从收敛阶的定义可以知道，收敛阶高的算法花费较少的时间；对于同阶
5、的算法，渐近常数小者花费较少的时间。,2.6 向量序列的极限,2.7 范数概念,2.8 常用向量范数,2.9 等价性定理、收敛速度,2.10 常用的矩阵范数,3 误差及数值算法的稳定性,误差的产生模型建立时因舍去次要矛盾会产生模型误差；模型中包含一些参数是通过仪表观测得到的，产生观测误差；算法必须在有限步内执行结束，这样需要将无穷过程截断为有限过程，产生截断误差；在用计算机实现数值算法的过程中，由于计算机表示浮点数采用的是固定有限字长，因而仅能够区分有限个信息，准确表示在某个有限范围内的某些有理数，不能准确表示数学中的所有实数，这样在计算机中表示的原始输入数据、中间计算数据、以及最终输出结果必
6、然产生误差，称此类误差为舍入误差。得到的计算结果是这些误差综合影响下的数据。,3.2 浮点数系,浮点数系是计算机常用的实数表示系统，一个浮点数的表示由正负号、有限小数形式的尾数、以及确定小数点位置的阶码三部分组成.设在某一浮点系统中,尾数占t位二进制数(未计算尾数的符号位),阶数占s位二进制数(未计算阶数的符号位),实数的浮点表示共需要ts2位的二进制数位.,3.3 溢出,3.4 单精度数,单精度实数用32位的二进制数据表示浮点数的这三个信息,其中数值符号和阶码符号各占1位,尾数占t=23位,阶码数值占s7位.这样，除零外,单精度实数的量级不大于1038不小于1038.当输入、输出或中间计算过
7、程中出现量级大于1038的数据时,因单精度实数无法正确表示该数据,将导致程序的非正常停止,称此现象为上溢(Overflow).而当出现量级小于10-38的非零数据时,一般计算机将该数置为零,精度损失,称此现象为下溢(Underflow).当数据有可能出现上溢或下溢时,可通过乘积因子变换数据,使之正常表示.67位有效数字,3.5 初值误差,由于误差传播研究困难，经常研究某种假设下误差的传播规律。如初值误差传播是在每一步都准确计算的假设下，即不考虑截断误差和由运算进一步引入的舍入误差，研究误差传播规律。,3.6 数值稳定性,舍入误差分析是非常繁杂困难的,而舍入误差不可避免,运算量又相当大,为此,人
8、们提出了数值稳定性这一概念对舍入误差是否影响产生可靠的结果进行定性分析.一个算法,如果在运算过程中舍入误差在一定条件下能够得到控制,或者舍入误差的增长不影响产生可靠的结果,则称该算法是数值稳定的,否则称其为数值不稳定.,3.7 数值稳定举例,不稳定算法结果,I1-I10近似值分别如下：0.0883920 0.0580400 0.0431333 0.0343333 0.0283333 0.0250000 0.0178571 0.0357143-0.0674603 0.4373016,算法2,Matlab 算出的精确解,稳定性不同于显著性,对算法的稳定性分析，其实就是给原始数据一个小扰动，分析计算
9、结果变化的程度,若很大则算法不稳定，若可以接受，则算法稳定.这里需要指出，算法的稳定性不同于建立模型过程中因素的显著性分析.,数值型算法设计注意事项,对于一个数值型算法除了其正确性（如收敛性）外，研究其效率（如收敛速度）、鲁棒性（如稳定性）是很重要的，同时程序设计或实现时如下几个问题也不可忽视：1）减少计算次数以缩短计算时间,2）避免相近数相减,避免相近数相减举例,3）尽可能避免大数吃小数,其它,4）避免很小的数做分母，防止溢出出现；5）正确使用实数相等的比较,5 数值型算法构造的常用基本思想,掌握数值型算法构造的基本思想将会有利于提出针对具体问题的有效快速算法,关于迭代的解释,在这个过程中，
10、首先我们用到了逼近的思想，将一个常量（方程的一个根）看成变量的极限，这个变量的每一个值是常量的近似值，不过它愈来愈近似的好.当然你也可以看出这个过程其实也用到了两个思想：动与静的思想，极限的思想.其次也用到了问题转换的思想，将函数的零点（方程的根）转换为另一个函数的不动点.最后借助不动点问题产生迭代序列，即使用迭代的思想产生逼近序列.,线性方程组,5.2 直与曲的思想,该法除了使用逼近的思想外，还用到了以直代曲的思想，用一系列的直线近似曲线，这些直线是曲线的一系列切线，特点是切点越来越和方程的一个根接近,举例,5.3 分段处理的思想,5.4 修正的思想,修正的思想在常微分方程数值解中使用非常之
11、多，它属于预估校正类算法,5.5 组合的思想,对精度较低的解近似进行组合，以期望得到近似精度高的解近似.一个典型的例子是龙贝格求积算法.,进一步说明,在这一组公式中，每一个式子的第二式就是用精度较低的两个近似通过组合得到精度较高的近似.这个组合的推出，由每一个公式的第一个式子可以看出是用了修正的思想，修正量是对分后改进量的一个分数倍数.它还用了以直代曲的思想、化整为零的思想，以得到复化梯形法计算公式,，,5.6 自适应的思想,自适应在算法构造中是非常重要的思想，它在构造算法时也同时兼顾了局部特征.以计算积分为例，当使用复化梯形公式时，我们总希望函数值变化较大的地方使用较多的节点，即使用较小的步
12、长，变化平坦的地方，步长较大一些，用较少的节点.显然用等步长的梯形公式效率就低，因为它忽视了函数变化的快慢，即局部特征.,算法的评价,同一问题可用不同算法解决，在分析了算法的可靠性之后，就需要对其效率进行分析，算法分析的目的在于选择合适的算法和改进算法.一个算法的效率评价主要从时间复杂度和空间复杂度来考虑.,6.1 时间复杂度,1）时间频度 算法执行所开销的时间，从理论上是很难算出来的，而上机运行测试可以得到时间花费的准确结果.但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中
13、语句执行次数多，它花费时间就多.一个算法中的语句执行次数称为算法时间频度，记为T(n)，其中 n是问题的规模，它是算法执行时所需存储空间的度量.符号T(n)表示算法的语句频度是问题规模的函数，它是算法需要完成多少工作的度量.,2）时间复杂度,在时间频度中，当问题规模n不断变化时，时间频度T(n)也会不断变化.为研究它变化时呈现的规律性，引入时间复杂度的概念.算法的时间频度是问题规模n的某个函数T(n)，若有某个辅助函数g(n)，使得当n趋近于无穷大时，T(n)/g(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(g(n)，称O(g(n)为算法的渐进时间复杂
14、度，简称时间复杂度.,举例,时间复杂度的渐进常数之比,说明,在算法中，若语句执行次数为一个常数，与求解规模没关系，则时间复杂度为O(1).即算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数，此类算法的时间复杂度是O(1).例子表明，在时间频度不相同时，时间复杂度也有可能相同.在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(g(n)简称为时间复杂度，其中函数g(n)一般选为算法中频度最大的语句频度.,常见的不同时间复杂度的效率,按数量级递增排列的时间复杂度有：常数阶O(1)，线性阶O(n)，线
15、性对数阶O(nlogn)，平方阶O(n2),立方阶O(n3)，指数阶O(2n)和 n!.随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低,比较图1,比较图2,比较图3,比较图4,给定数据规模n，执行给定时间复杂度的算法耗时比较,给定数据规模n，执行给定时间复杂度的算法耗时比较,6.2 问题的规模,时间复杂度是问题规模n的函数.我们将标识问题类中不同问题大小的参数定义为问题的规模.如计算两个向量的点乘积，那么一个向量的分量个数n就是它的规模参数；计算两个矩阵的乘法，矩阵的行数和列数就是该问题的规模；如若计算方阵的乘法，它的行数或者列数就是该问题规模；求解一个线性方程组，线形方
16、程组的阶数就是其规模；对一组数进行排序，这一组数的个数就是其规模，等等.问题的规模不同于求解一个问题的算法的空间复杂度，算法的空间复杂度涉及到除原始数据外所需要额外增加的存储空间.原始数据量是问题规模的单调增加函数,6.3 时间复杂度分析,考虑算法的渐进时间复杂度，即随着问题规模的增大时间频度的变化趋势，通常时间耗费是问题规模的单调增加函数，因而算法中的一些与问题规模无关的语句执行时间可以不予考虑，因为该语句的频度是O(1).由于编译系统对循环语句中循环次数的控制在编译时已经计算好，所以时间复杂性分析时可以不予考虑.当对渐进常数的大小不关心，仅考虑其渐进阶数时，只需分析循环中某一个语句的执行频
17、度.这也从另一个侧面说明数量级分析并不是算法分析的全部内容，它仅考虑了数量级最高项的级，忽略其系数，更忽略了低阶项.,例1 计算两个向量点乘积的算法,问题规模为n，全部统计时算法复杂度为O(n+1)，忽略循环外的语句时算法复杂度为O(n)，显然他们的量级相同.这里对步进循环语句只考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分,例2 计算一个n维行向量和两个n阶方矩阵的乘积.,问题规模为n，算法时间复杂度为O(2n2+2n)，忽略外循环时，算法复杂度为O(2n2)，显然它们具有相同的渐进阶，且渐进常数相同；如果仅考虑内循环的一条语句，算法复杂度为O(n2)，虽然依然保
18、证同阶，但渐进常数发生了改变,例3 矩阵乘积,例4 计算n阶方阵下三角部分元素之和,算法复杂度为O(n(n+1)/2+1).该算法分析时，内循环参数虽没有和问题规模直接相关，但它和外循环参数i相关，i与问题规模是相关的，这样内循环参数j间接和问题规模相关.算法分析时一定得注意循环控制参数与问题规模间的间接相关性.,例5 计算向量分量的正弦值的最大值,问题规模为n，算法复杂度O(3n-2).这里统计语句频度时，没有区分正弦值计算与比较、数值操作上执行时间的差异，显然后者花费较少的时间.这也就是说即使每一个语句的频度都统计上，算法复杂度也是一个粗略的估计.如果进一步考虑正弦值如何计算，那么算法的复
19、杂度量级不会变化，但渐进常数必然改变，这是由于计算一个正弦值需要确定的时间，与问题规模无关.可见算法描述的越精细，分析出的时间频度越能反映时间耗费状态.,说明2,语句“max=t”实际上是条件执行的，只有条件“tmax”成立时才执行.t是有原始数据计算出的，这说明对于一个具体的算例，即问题类中的一个具体问题，语句频度还与初始数据有关.类似的问题还很多，如匹配查找问题、排序问题等.上面我们实际上假设条件语句“max=t”一定执行，也就是说考虑的是最坏的一种情形，所得复杂性结论对于问题类中所有问题来说都是正确的(作为其上界).,说明3,最坏情况下的时间复杂度称为问题类的最坏时间复杂度.一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度.正如前面所讨论的，这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比它更长.另一种思路是使用平均复杂度，平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间.如对于算例5，语句“max=1”、“t=sin(x(i)”、“tmax?”是一定执行的，对于语句“max=t”是否执行的概率相等，这样算法复杂度为O(1+2(n-1)+(n-1)/2)=O(5(n-1)/2+1).和最坏时间复杂度相比，具有相同的量级，渐进常数不同.,
