第八章算法基础

《第八章算法基础》由会员分享，可在线阅读，更多相关《第八章算法基础（65页珍藏版）》请在装配图网上搜索。

1、第八章 算法基础 西北工业大学应用数学系聂玉峰1.算法概念算法概念l数学建模竞赛的过程l算法的概念l算法的分类l算法的评价1.1 建模竞赛的过程建模竞赛的过程l实际上是命题人（某个领域的专家）提出实际问题l参赛人首先读题，分析问题，依照自己的理解准确阐述问题；l辨析问题中的主要矛盾和次要矛盾，并在合理假设的条件下，运用各种数学理论、工具和方法，建立起问题中不同量之间的约束关系，进而得到完备的数学模型；l在研究模型解的存在性与惟一性l如何求其解 l利用解对模型的正确性进行评价。1.2 算法的概念算法的概念l当数学模型的分析解得不到时，使用计算机进行求解。我们不会做的计算机肯定不会做，只有当我们会

2、做，但因为数据计算量太大时，把自己的求解过程（算法）编写成程序，计算机将其编译、运行得到计算结果。l 所谓（串行）算法就是求解一个问题类的无二义性的有穷过程，这里过程明确无歧义的描述由有限操作（算术运算、逻辑运算、字符运算、读写操作等）及有限操作对象合成的按一定顺序执行的有限序列。l原始的可以变化的有限操作对象就是有限输入数据，它所有可能允许的变化构成求解的问题类。1.3 算法的分类算法的分类l对给定的输入数据，算法运行后得到的数据结果也是有限的，这样可以把算法看成有限输入数据和有限输出结果之间的对应关系。l 将以浮点算术运算为主的算法称为数值型算法，如线性方程组的求解，数值积分的计算，微分方

3、程初边值问题的求解等。其它算法称为非数值型算法，如排序问题，匹配查找问题等。1.4 算法的评价算法的评价l算法在保证可靠的大前提下再评价其优劣才是有价值的。l数值型算法的可靠性算法的收敛性、稳定性、误差估计等算法必须在有限的时间内得到计算结果，如果某问题类的一个求解过程是无限长，需要将其截断得到求解算法，并产生截断截断误差误差。算法的收敛性就是研究当运行时间趋于无限长时，算法的解是否趋于真实解，即截断误差是否趋于零。l非数值型算法的可靠性更为强调对于整体问题类算法计算结果的正确性。算法的评价（算法的评价（2）l评价一个可靠算法的优劣，应该考虑其时间复杂度（计算机运行时间）、空间复杂度（占据计算

4、机存储空间的多少）以及逻辑复杂度（影响程序开发的周期以及维护）。2数值型算法的收敛阶数值型算法的收敛阶 l迭代迭代是构造数值问题算法的基本思想之一，迭代的结果是得到问题解的一个近似序列.l如果对于问题类中任一问题，迭代次数k趋于无穷大时序列极限存在，并且就是该问题的准确解，则称该迭代算法收敛到问题的解。2.1 数列收敛阶的定义数列收敛阶的定义定义定义 1 对于一个收敛的数列)(*0nyynn，如果存在常数1p和0c，使得有 cyyyypnnn*1lim 成立（当 p1 时要求 c1时称为超线性收敛 p2时为平方收敛或二次收敛。如几何级数02/1nn、03/1nn都是线性收敛的，但前者的渐近常数

5、大于后者的渐近常数，故后者收敛更快一些。2.3 2阶收敛举例阶收敛举例级数022/1nn平方收敛 102/102/1lim2221nnn 2.4 算法的收敛阶算法的收敛阶l类似地，如果收敛的数列是由迭代算法产生的，定义数列的收敛阶为算法的收敛阶。不过需要注意，算法是对问题类的算法，不是针对一个特定问题的，这样算法的收敛阶应该是由该算法生成的序列都具有的共同特征。2.5 时间花费与收敛速度时间花费与收敛速度l对于不同的算法，若每一迭代步的时间花费相当，从收敛阶的定义可以知道，收敛阶高的算法花费较少的时间；对于同阶的算法，渐近常数小者花费较少的时间。2.6 向量序列的极限向量序列的极限多变量问题的

6、迭代算法，产生的近似解序列是向量序列0)(kkx Tknkkkxxx),()()(2)()(1x 定义定义 2 如存在向量Tnxxx),(*2*1*x，使向量序列0)(kkx的各分量构成的数列收敛到向量 x*的对应分量，即),2,1(lim*)(njxxjkjk 称向量序列0)(kkx收敛到向量 x*.2.7 范数概念范数概念定义定义 3 定义在 Rn上的实值函数，如果满足：1）非负性：nRuu0;0uu 0 2）齐次性：RrRrrn,uuu 3）三角不等式：nRvuvuvu,则称函数是该向量空间上的一种范数。2.8 常用向量范数常用向量范数inix1maxxniix11x2/1122niix

7、x2.9 等价性定理、收敛速度等价性定理、收敛速度定理定理 1 向量序列0)(kkx收敛到向量 x*的充分必要条件是存在某种向量范数，使得有 0lim*)(xxkk cpkkk*)(*)1(limxxxx2.10 常用的矩阵范数常用的矩阵范数niijnja111maxAnjijnia11maxA)(max2AAAT3 误差及数值算法的稳定性误差及数值算法的稳定性l误差的产生模型建立时因舍去次要矛盾会产生模型误差模型误差；模型中包含一些参数是通过仪表观测得到的，产生观测误差观测误差；算法必须在有限步内执行结束，这样需要将无穷过程截断为有限过程，产生截断误差截断误差；在用计算机实现数值算法的过程中

8、，由于计算机表示浮点数采用的是固定有限字长，因而仅能够区分有限个信息，准确表示在某个有限范围内的某些有理数，不能准确表示数学中的所有实数，这样在计算机中表示的原始输入数据、中间计算数据、以及最终输出结果必然产生误差，称此类误差为舍入误差舍入误差。l 得到的计算结果是这些误差综合影响下的数据。3.2 浮点数系浮点数系l浮点数系是计算机常用的实数表示系统，一个浮点数的表示由正负号、有限小数形式的尾数、以及确定小数点位置的阶码三部分组成.l设在某一浮点系统中,尾数占t位二进制数(未计算尾数的符号位),阶数占s位二进制数(未计算阶数的符号位),实数的浮点表示共需要ts2位的二进制数位.3.3 溢出溢出

9、浮点数系所能够表示的绝对值最大的数，即上溢界上溢界2lg)12(12102ss 当非零数很小时用零表示，能够表示的绝 对 值 最 小 的 数，即 下 溢 界下 溢 界 是2lg22102ss.3.4 单精度数单精度数l单精度实数用32位的二进制数据表示浮点数的这三个信息,其中数值符号和阶码符号各占1位,尾数占t=23位,阶码数值占s7位.这样，除零外,单精度实数的量级不大于1038不小于1038.l当输入、输出或中间计算过程中出现量级大于1038的数据时,因单精度实数无法正确表示该数据,将导致程序的非正常停止,称此现象为上溢上溢(Overflow).l而当出现量级小于1038的非零数据时,一般

10、计算机将该数置为零,精度损失,称此现象为下溢下溢(Underflow).l当数据有可能出现上溢或下溢时,可通过乘积因子变换数据,使之正常表示.67位有效数字3.5 初值误差初值误差l由于误差传播研究困难，经常研究某种假设下误差的传播规律。如初值误差传播初值误差传播是在每一步都准确计算的假设下，即不考虑截断误差和由运算进一步引入的舍入误差，研究误差传播规律。n1ii*i*n*1i*)(,()(xxxxfyyyen1i*i*i*n*1i*i*)(),()()(xxexxfyxyyeyer3.6 数值稳定性数值稳定性l舍入误差分析是非常繁杂困难的,而舍入误差不可避免,运算量又相当大,为此,人们提出了

11、数值稳定性这一概念对舍入误差是否影响产生可靠的结果进行定性分析.l一个算法,如果在运算过程中舍入误差在一定条件下能够得到控制,或者舍入误差的增长不影响产生可靠的结果,则称该算法是数值稳定数值稳定的,否则称其为数值不稳定.3.7 数值稳定举例数值稳定举例dxxxInn105),2,1(511nInInn1823216.056ln51100dxxI不稳定算法结果不稳定算法结果I1-I10近似值分别如下：0.0883920 0.0580400 0.0431333 0.0343333 0.0283333 0.0250000 0.0178571 0.0357143 -0.0674603 0.437301

12、6)1(5156)1(611010ndxxIdxxnnnn)0.0181818 0.0151515,()55/1,66/1(10I算法算法290.00873015216121512120I511nnInI0.0153675510I8912760.01536754 2520/44868195235/6ln9765625Matlab 算出的精确解稳定性不同于显著性稳定性不同于显著性l 对算法的稳定性分析，其实就是给原始数据一个小扰动，分析计算结果变化的程度,若很大则算法不稳定，若可以接受，则算法稳定.这里需要指出，算法的稳定性不同于建立模型过程中算法的稳定性不同于建立模型过程中因素的显著性分析因素

13、的显著性分析.4数值型算法设计注意事项数值型算法设计注意事项 4对于一个数值型算法除了其正确性（如收敛性）外，研究其效率（如收敛速度）、鲁棒性（如稳定性）是很重要的，同时程序设计或实现时如下几个问题也不可忽视：51）减少计算次数以缩短计算时间 6.36.36.36.36.36.36.36.31684233013210111)(axaxxaxaxaxaaxaxaxannnnnnnn2）避免相近数相减）避免相近数相减如 x的近似值 x*=3.5468,y的近似值 y*=3.5472,则 z=x-y的近似值 z*=0.0004 最多有 1 位有效数字.也就是说相近数相减必然快速的削减有效数字的位数.

14、避免相近数相减举例避免相近数相减举例)(11111xxxx，1x xxxx111，1x xxxx1lnln)1ln(，1x)1ln()1ln(22xxxx，1x!5!3sin53xxxx，1x 3）尽可能避免大数吃小数）尽可能避免大数吃小数)10(,9876543211000000001iii100000000999000012000001000011000001987654321iiiiii其它其它l4）避免很小的数做分母，防止溢出出现；l5）正确使用实数相等的比较由于误差的存在，实数的相等比较应该换成不等式，如将判断yx 换成epsyx，其中 eps 是很小的数，也可以是最小的非零机器数

15、5 数值型算法构造的常用基本思想数值型算法构造的常用基本思想 掌握数值型算法构造的基本思想将会有利于提出针对具体问题的有效快速算法 5.1 迭代思想 在求解非线性方程0)(xf时，恒等变形成)(xx，给解的一个初始近似0 x，构造迭代过程 产生迭代序列迭代序列0kkx.如果有极限)(*kxxk，)(*xx，得到原方程的一个解*x.关于迭代的解释关于迭代的解释在这个过程中，首先我们用到了逼近的思想逼近的思想，将一个常量（方程的一个根）看成变量的极限，这个变量的每一个值是常量的近似值，不过它愈来愈近似的好.当然你也可以看出这个过程其实也用到了两个思想：动与静的思想，极限的思想.其次也用到了问题转换

16、的思想问题转换的思想，将函数的零点（方程的根）转换为另一个函数的不动点.最后借助不动点问题产生迭代序列，即使用迭代的思迭代的思想想产生逼近序列.线性方程组线性方程组将线性方程组bAx 恒等变换成gBxx，定义迭代过程 gBxx)1()(kk，由初始的近似解向量)0(x便可以产生近似解向量序列 5.2 直与曲的思想直与曲的思想 非线性方程0)(xf之所以难解是因为函数)(xf非线性，由它定义了一条曲线.如果知道方程根的一个近似，就可以在该根附近该根附近将非线性问题线性化，即将曲线直线化，用直线和 x 轴的交点作为曲线和 x轴的交点，即得到方程根的又一个近似，这个过程不断进行，变产生了根的一个近似

17、序列.这其实就产生了求解非线性方程的牛顿法 )(/)(1kkkkxfxfxx.该法除了使用逼近的思想外，还用到了以直代曲直代曲的思想，的思想，用一系列的直线近似曲线，这些直线是曲线的一系列切线，特点是切点越来越和方程的一个根接近 举例举例求解常微分方程初值问题 00)(),(yxyyxfy 的欧拉折线法 ),()(11nnnnnnyxfxxyy 典型的以折线段近似曲线的.5.3 分段处理的思想分段处理的思想 已知一组采样点niixf0)(值，求非采样点函数值的一种方法就是插值法，用不超过 n 次多项式的函数值近似之.但当数据量很大时，不能构造高次插值，一是计算量大，二是高次插值不保证收敛，也不

18、稳定.采用分段处理的思想分段处理的思想解决该问题就很好,即采用分段的低次插值，既能保证稳定，又收敛，计算量还小.5.4 修正的思想修正的思想 l修正的思想在常微分方程数值解中使用非常之多，它属于预估校正类算法 有线性方程组解bAx 的一个近似)(kx，一般说来残差)()(kkAxbr不等于零向量，对之进行修正得到更好的近似)(1)()1(kkkrDxx，式中矩阵D是由系数矩阵A的对角元构成的矩阵，这就是所谓的逐个超松弛迭代法（SOR）.它采用的就是给粗糙的解向量一个修正量修正量（残差），以得到更好的解近似。5.5 组合的思想组合的思想 l对精度较低的解近似进行组合，以期望得到近似精度高的解近似

19、.一个典型的例子是龙贝格求积算法.计算积分badxxf)(，将区间,ban2等分用梯形公式计算的结果记为)(nT，龙贝格求积算法公式如下：)(31)2(34)()2(31)2()2(nTnTnTnTnTnS)(151)2(1516)()2(151)2()2(nSnSnSnSnSnC)(631)2(6364)()2(631)2()2(nCnCnCnCnCnR进一步说明进一步说明l在这一组公式中，每一个式子的第二式就是用精度较低的两个近似通过组合组合得到精度较高的近似.这个组合的推出，由每一个公式的第一个式子可以看出是用了修正的思想修正的思想，修正量是对分后改进量的一个分数倍数.它还用了以直代曲的

20、思想、直代曲的思想、化整为零的思想化整为零的思想，以得到复化梯形法计算公式 ，)()()(2)(11bfxfafhnTniinabh5.6 自适应的思想自适应的思想 l自适应在算法构造中是非常重要的思想，它在构造算法时也同时兼顾了局部特征局部特征.以计算积分为例，当使用复化梯形公式时，我们总希望函数值变化较大的地方使用较多的节点，即使用较小的步长，变化平坦的地方，步长较大一些，用较少的节点.显然用等步长的梯形公式效率就低，因为它忽视了函数变化的快慢，即局部特征.6 6算法的评价算法的评价 l 同一问题可用不同算法解决，在分析了算法的可靠性之后，就需要对其效率进行分析，算法分析的目的在于选择合适

21、的算法和改进算法.一个算法的效率评价主要从时间复杂度和空间复杂度来考虑.6.1 时间复杂度时间复杂度1）时间频度 算法执行所开销的时间，从理论上是很难算出来的，而上机运行测试可以得到时间花费的准确结果.但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多.一个算法中的语句执行次数称为算法时间频度时间频度，记为T(n)，其中 n是问题的规模，它是算法执行时所需存储空间的度量.符号T(n)表示算法的语句频度是问题规模的函数，它是算法需要完成多少工作的度量

22、.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)为算法的渐进时间复杂度渐进时间复杂度，简称时间时间复杂度复杂度.举例举例)(4503)(331nOnnnT，)(34)(332nOnnnT，渐进常数不同，前者的渐进常数为3，后者的渐进常数为 4，当问题规模较大时，前者花费的时间基本

23、上是后者的 3/4 倍.但当问题规模较小时，这个结论并不正确.图 1表明当 n 小于 7 时，T2(n)花费较少的时间，否则 T1(n)更有效.渐进常数之比示于图 2 中.时间复杂度的渐进常数之比说明l在算法中，若语句执行次数为一个常数，与求解规模没关系，则时间复杂度为O(1).即算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数，此类算法的时间复杂度是O(1).l例子表明，在时间频度不相同时，时间复杂度也有可能相同.l在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(g(n)简称为时间复杂度，

24、其中函数g(n)一般选为算法中频度最大的语句频度.常见的不同时间复杂度的效率 按数量级递增排列的时间复杂度有：常数阶O(1)，线性阶O(n)，线性对数阶O(nlogn)，平方阶O(n2),立方阶O(n3)，指数阶O(2n)和 n!.随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低 比较图1比较图2比较图3比较图4给定数据规模n，执行给定时间复杂度的算法耗时比较执行给定时间复杂度的算法耗时比较n102030log10n0.000 001 0秒0.000 001 3秒 0.000 001 5秒n0.000 01秒0.000 02秒0.000 03秒n20.000 1秒0.000

25、 4秒0.000 9秒n30.001秒0.008秒0.027秒n50.1秒3.2秒24.3秒2n0.001秒1.0秒17.9分3n0.059秒58分6.5年n!3.6秒771.5世纪8.4E16世纪给定数据规模n，执行给定时间复杂度的算法耗时比较执行给定时间复杂度的算法耗时比较n405060log10n0.000 001 6秒0.000 001 7秒 0.000 001 8秒n0.000 04秒0.000 05秒0.000 06秒n20.001 6秒0.002 5秒0.003 6秒n30.064秒0.125秒0.216秒n51.7分5.2分13.0分2n12.7天35.7年366世纪3n3 8

26、55世纪2E8世纪1.3E13世纪n!2.6E32世纪9.6E48世纪2.6E66世纪6.2 6.2 问题的规模问题的规模 l时间复杂度是问题规模n的函数.我们将标识问题类中不同问题大小的参数定义为问题的规模问题的规模.如计算两个向量的点乘积，那么一个向量的分量个数n就是它的规模参数；计算两个矩阵的乘法，矩阵的行数和列数就是该问题的规模；如若计算方阵的乘法，它的行数或者列数就是该问题规模；求解一个线性方程组，线形方程组的阶数就是其规模；对一组数进行排序，这一组数的个数就是其规模，等等.l问题的规模不同于求解一个问题的算法的空间复杂度，算法的空间复杂度涉及到除原始数据外所需要额外增加的存储空间.

27、原始数据量是问题规模的单调增加函数 6.3 6.3 时间复杂度分析时间复杂度分析 l考虑算法的渐进时间复杂度，即随着问题规模的增大时间频度的变化趋势，通常时间耗费是问题规模的单调增加函数，因而算法中的一些与问题规模无关的语句执行时间可以不予考虑，因为该语句的频度是O(1).由于编译系统对循环语句中循环次数的控制在编译时已经计算好，所以时间复杂性分析时可以不予考虑.l当对渐进常数的大小不关心，仅考虑其渐进阶数时，只需分析循环中某一个语句的执行频度.这也从另一个侧面说明数量级分析并不是算法分析的全部内容数量级分析并不是算法分析的全部内容，它仅考虑了数量级最高项的级，忽略其系数，更忽略了低阶项.)5

28、0043()5004()50043(2333nnOnnOnnO例例1 1 计算两个向量点乘积的算法计算两个向量点乘积的算法 l问题规模为n，全部统计时算法复杂度为O(n+1)，忽略循环外的语句时算法复杂度为O(n)，显然他们的量级相同.这里对步进循环语句只考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分输入参数：向量),(21nxxxx，向量),(21nyyyy 和 规模 n.输出参数：点积 add.算法：add=0;1 For i=1:n add=add+x(i)*y(i)n end i 例例2 2 计算一个计算一个n n维行向量和两个维行向量和两个n n阶方矩阵的

29、乘积阶方矩阵的乘积.l问题规模为n，算法时间复杂度为O(2n2+2n)，忽略外循环时，算法复杂度为O(2n2)，显然它们具有相同的渐进阶，且渐进常数相同；如果仅考虑内循环的一条语句，算法复杂度为O(n2)，虽然依然保证同阶，但渐进常数发生了改变 输入参数：向量),(21nxxxx，矩阵nnija)(A，nnijb)(B，规模 n.输出参数：向量),(21nyyyy 向量),(21nzzzz 算法：For i=1:n y(i)=0 n z(i)=0 n for j=1:n y(i)=y(i)+x(j)*a(i,j)n2 z(i)=z(i)+x(j)*b(i,j)n2 end j end i 例例

30、3 3 矩阵乘积矩阵乘积例 3 求矩阵nmRA和矩阵knRB的乘积.输入参数：矩阵nmija)(A，knijb)(B，问题规模参数 n，m，k.输出参数：向量kmijc)(C 算法：For i=1:m For j=1:k c(i,j)=0 km end j end i For i=1:m For j=1:k For l=1:n c(i,j)=c(i,j)+a(i,l)*b(l,j)nkm end l end j end i 问题规模为(n,m,k)，算法复杂度为 O(nkm+km).例例4 4 计算计算n n阶方阵下三角部分元素之和阶方阵下三角部分元素之和 l 算法复杂度为O(n(n+1)/2

31、+1).该算法分析时，内循环参数虽没有和问题规模直接相关，但它和外循环参数i相关，i与问题规模是相关的，这样内循环参数j间接和问题规模相关.算法分析时一定得注意循环控制参数与问题规模间的间接相关性.输入参数：矩阵nnija)(A，问题规模参数 n.输出参数：add 算法：add=0 1 for i=1:n for j=1:i add=add+a(i,j)i(i=1:n)end j end i 例例5 5 计算向量分量的正弦值的最大值计算向量分量的正弦值的最大值 l 问题规模为n，算法复杂度O(3n-2).这里统计语句频度时，没有区分正弦值计算与比较、数值操作上执行时间的差异，显然后者花费较少的

32、时间.这也就是说即使每一个语句的即使每一个语句的频度都统计上，算法复杂度也是一频度都统计上，算法复杂度也是一个粗略的估计个粗略的估计.如果进一步考虑正弦值如何计算，那么算法的复杂度量级不会变化，但渐进常数必然改变，这是由于计算一个正弦值需要确定的时间，与问题规模无关.可见算法描述的越精细，分析出的时间频度越能反映时间耗费状态.输入参数：向量),(21nxxxx问题规模 n 输出参数：最大值 max 算法：max=sin(x(1)1 for i=2:n t=sin(x(i)n-1 if tmax n-1 max=t n-1 endif end i 说明说明2 2l 语句“max=t”实际上是条件

33、执行的，只有条件“tmax”成立时才执行.t是有原始数据计算出的，这说明对于一个具体的算例，即问题类中的一个具体问题，语句频度还与初始数据有关.类似的问题还很多，如匹配查找问题、排序问题等.上面我们实际上假设条件语句“max=t”一定执行，也就是说考虑的是最坏的一种情考虑的是最坏的一种情形形，所得复杂性结论对于问题类中所有问题来说都是正确的(作为其上界).输入参数：向量),(21nxxxx问题规模 n 输出参数：最大值 max 算法：max=sin(x(1)1 for i=2:n t=sin(x(i)n-1 if tmax n-1 max=t n-1 endif end i 说明说明3 3l最

34、坏情况下的时间复杂度称为问题类的最坏时间复杂度最坏时间复杂度.一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度.正如前面所讨论的，这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比它更长.l另一种思路是使用平均复杂度，平均时间复杂度平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间.如对于算例5，语句“max=1”、“t=sin(x(i)”、“tmax?”是一定执行的，对于语句“max=t”是否执行的概率相等，这样算法复杂度为O(1+2(n-1)+(n-1)/2)=O(5(n-1)/2+1).和最坏时间复杂度相比，具有相同的量级，渐进常数不同.