数学建模简明教程教案.ppt

《数学建模简明教程教案.ppt》由会员分享，可在线阅读，更多相关《数学建模简明教程教案.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数学建模简明教程 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第八章第八章 算法基础算法基础一、一、算法概念算法概念二、数值型算法构造的常用思想二、数值型算法构造的常用思想三、数值算法可靠性三、数值算法可靠性 四、数值型算法设计注意事项四、数值型算法设计注意事项 五、五、算法的评价算法的评价目录下页返回上页结束 1.1 数学建模竞赛的过程数学建模竞赛的过程 1.3 算法的分类算法的分类 1.4 算法的评价算法的评价 1.2 算法的概念算法的概念 一、算法概念一、

2、算法概念目录下页返回上页结束 1.1 数学建模竞赛的过程数学建模竞赛的过程 (1)提出问题：提出问题：命题人（某个领域的专家）提出命题人（某个领域的专家）提出 (2)分析问题：分析问题：参赛人首先读题，分析问题，依参赛人首先读题，分析问题，依(3)建立模型：建立模型：辨析问题中的主要矛盾和次要矛辨析问题中的主要矛盾和次要矛 (4)模型求解：模型求解：研究解的存在性与惟一性，寻找研究解的存在性与惟一性，寻找 目录下页返回上页结束实际问题实际问题；照自己的理解准确阐述问题照自己的理解准确阐述问题；间的约束关系，进而得到完备的数学模型；间的约束关系，进而得到完备的数学模型；理论、工具和方法，建立起问

3、题中不同量之理论、工具和方法，建立起问题中不同量之盾，盾，并在合理假设的条件下，运用各种数学并在合理假设的条件下，运用各种数学求解方法，利用解对模型的正确性进行评价求解方法，利用解对模型的正确性进行评价.1.2 算法的概念算法的概念 定义定义 串行串行算法算法就是求解一个问题类的无二义性就是求解一个问题类的无二义性定义定义 原始的可变化的原始的可变化的有限操作对象有限操作对象就是有限输入就是有限输入注注 对给定的输入数据，算法运行后得到的数据对给定的输入数据，算法运行后得到的数据的有穷过程，这里过程明确无歧义的描述由有限的有穷过程，这里过程明确无歧义的描述由有限操作（算术、逻辑、字符运算和读写

4、操作等）及操作（算术、逻辑、字符运算和读写操作等）及有限操作对象合成的按一定顺序执行的有限序列有限操作对象合成的按一定顺序执行的有限序列.数据，它所有可能允许的变化构成求解的数据，它所有可能允许的变化构成求解的问题类问题类.结果也是有限的，结果也是有限的，这样可以把算法看成有限输入这样可以把算法看成有限输入数据和有限输出结果之间的对应关系数据和有限输出结果之间的对应关系.目录下页返回上页结束 1.3 算法的分类算法的分类 定义定义 根据对象的不同可以将算法分为根据对象的不同可以将算法分为数值型数值型目录下页返回上页结束算法算法和和非数值型算法非数值型算法.将以浮点算术运算为主将以浮点算术运算为

5、主的算法称为的算法称为数值型算法数值型算法，非数值型算法非数值型算法一般一般包括线性表、栈、队列和串、树、图，排序、包括线性表、栈、队列和串、树、图，排序、查找等数据处理方面的算法查找等数据处理方面的算法.1.4 算法的评价算法的评价 优劣优劣才是有价值的才是有价值的.(1)算法可靠性评价算法可靠性评价 数值型算法：数值型算法：收敛性、稳定性、误差估计；收敛性、稳定性、误差估计；非数值型算法：强调对于整体问题类算法非数值型算法：强调对于整体问题类算法计算结果的正确性计算结果的正确性.(2)算法优劣评价算法优劣评价时间复杂度，空间复杂度，逻辑复杂度时间复杂度，空间复杂度，逻辑复杂度.注注 算法在

6、保证可靠的大前提下再评价其算法在保证可靠的大前提下再评价其目录下页返回上页结束二、构造数值型算法的常用思想二、构造数值型算法的常用思想了解数值型算法构造的常用基本思想，有利于了解数值型算法构造的常用基本思想，有利于针对自己研究的具体问题提出有效可靠算法针对自己研究的具体问题提出有效可靠算法.2.1 迭代的思想迭代的思想 2.2 直与曲的思想直与曲的思想 2.3 分段处理的思想分段处理的思想 2.4 修正的思想修正的思想 2.5 组合的思想组合的思想 2.6 自适应的思想自适应的思想 常用基本思想：常用基本思想：目录下页返回上页结束 2.1 迭代的思想迭代的思想 非线性方程非线性方程 等价变形等

7、价变形迭代格式迭代格式 产生迭代序列产生迭代序列如果如果则可以得到方程的解则可以得到方程的解.线性方程组线性方程组等价变形等价变形迭代格式迭代格式产生迭代向量序列产生迭代向量序列如果如果则可得到方程组的解则可得到方程组的解.目录下页返回上页结束 2.2 直与曲的思想直与曲的思想 大多数曲线就一小范围来看大致可以看成是大多数曲线就一小范围来看大致可以看成是直线直线.非线性方程非线性方程 的根可视为函数的根可视为函数 与与 轴的交点轴的交点.在交点附近可以用在交点附近可以用 直线代替曲线直线代替曲线 ，相应地用直线与，相应地用直线与 x*Oyx 轴的交点轴的交点 代替曲线与代替曲线与 轴的交点轴的

8、交点 .牛顿迭代法牛顿迭代法目录下页返回上页结束例例 求解常微分方程初值问题求解常微分方程初值问题的欧拉折线法的欧拉折线法 典型的以折线段近似曲线的典型的以折线段近似曲线的.xyy(x)xnxn+1PnPn+1目录下页返回上页结束 2.3 分段处理的思想分段处理的思想 已知一组采样点已知一组采样点 值，求非采样点处值，求非采样点处 函数值的一种方法就是插值法函数值的一种方法就是插值法.当当 较大时较大时,如果直接采用高次插值如果直接采用高次插值一是计算量大一是计算量大;二是高次插值不保证收敛，也不稳定二是高次插值不保证收敛，也不稳定.采用采用分段处理的思想分段处理的思想就能很好解决该问题就能很

9、好解决该问题,即采用分段的低次插值，既能保证稳定，又即采用分段的低次插值，既能保证稳定，又收敛，计算量还小收敛，计算量还小.目录下页返回上页结束 2.4 修正的思想修正的思想 记记 为线性方程组为线性方程组 的一个近似，一般的一个近似，一般说来残差说来残差 不等于零向量，对之不等于零向量，对之 进行修正得到更好的近似进行修正得到更好的近似 式中矩式中矩阵阵是由是由的的对对角元素构成的矩角元素构成的矩阵阵 逐个超松弛逐个超松弛迭代法迭代法注注 此方法采用的就是给粗糙的解向量一个此方法采用的就是给粗糙的解向量一个修正量修正量，以得到更好的解近似以得到更好的解近似.目录下页返回上页结束 2.5 组合

10、的思想组合的思想 对精度较低的解近似进行组合，以期望得到对精度较低的解近似进行组合，以期望得到近似精度高的解近似近似精度高的解近似.例例 龙贝格求积算法龙贝格求积算法.计算积分计算积分 将区间将区间 等分等分 个子个子区间区间,采用复化梯形公式得到的近似值为采用复化梯形公式得到的近似值为目录下页返回上页结束 2.6 自适应的思想自适应的思想 自适应在算法构造中是非常重要的思想，它在自适应在算法构造中是非常重要的思想，它在构造算法时也同时兼顾了局部特征构造算法时也同时兼顾了局部特征.小小的步长，变化平坦的地方，步长较大一些的步长，变化平坦的地方，步长较大一些.例例 当使用复化梯形公式计算积分时，

11、在函数当使用复化梯形公式计算积分时，在函数值变化较大的地方使用较多的节点，即使用较值变化较大的地方使用较多的节点，即使用较xyxyf(x)f(x)自适应自适应非自适应非自适应目录下页返回上页结束三、数值算法的可靠性三、数值算法的可靠性 本节介绍算法可靠性的三个方面：本节介绍算法可靠性的三个方面：(1)算法的收敛性算法的收敛性：研究当运行时间趋于无限研究当运行时间趋于无限长时，算法的解是否趋于真实解，即截断长时，算法的解是否趋于真实解，即截断误差是否趋于零误差是否趋于零.(2)算法的稳定性算法的稳定性：就是当原始数据有小的误就是当原始数据有小的误差时，算法计算出的结果是否也有小扰动，差时，算法计

12、算出的结果是否也有小扰动，而不是很大的变化而不是很大的变化.(3)误差估计误差估计：其其用途是设计循环的终止条件，用途是设计循环的终止条件，让数值解满足给定的精度要求让数值解满足给定的精度要求.目录下页返回上页结束 3.1 近似解序列的收敛性近似解序列的收敛性 迭代迭代是构造数值问题算法的基本思想之一，是构造数值问题算法的基本思想之一，迭代得到问题解的一个近似序列迭代得到问题解的一个近似序列 ，如果如果 ，且，且 就是原问题的解，就是原问题的解，则称该迭代算法收敛到问题的解则称该迭代算法收敛到问题的解.多变量问题的迭代算法，产生的近似解序列多变量问题的迭代算法，产生的近似解序列是向量序列是向量

13、序列 ，目录下页返回上页结束 3.1.1 向量序列收敛定义向量序列收敛定义 定义定义 如存在向量如存在向量 使向量序使向量序列列 的各分量构成的数列收敛到向量的各分量构成的数列收敛到向量的对应分量，即的对应分量，即 称称向量序列向量序列 收敛到向量收敛到向量 .注注 上述收敛被称为按分量收敛，此定义虽然上述收敛被称为按分量收敛，此定义虽然直观，但不便于理论分析，因此引入向量按范直观，但不便于理论分析，因此引入向量按范数收敛的定义数收敛的定义.目录下页返回上页结束 3.1.2 范数概念范数概念 定义定义 定义在定义在 上的实值函数上的实值函数 ，如果满足，如果满足1)非负性，即非负性，即2)齐次

14、性，即齐次性，即3)三角不等式，即三角不等式，即则称函数则称函数 是该向量空间上的一种是该向量空间上的一种范数范数.注注 范数概念是对距离的一种抽象和推广范数概念是对距离的一种抽象和推广.目录下页返回上页结束 3.1.3 常用向量范数常用向量范数 对于向量对于向量 ，常用的范数有，常用的范数有 例例 计算向量计算向量 的各种范数的各种范数 解解目录下页返回上页结束 3.1.4 常用的矩阵范数常用的矩阵范数 定义定义 对于矩阵对于矩阵A，常用的范数有，常用的范数有 行和范数行和范数列和范数列和范数谱范数谱范数目录下页返回上页结束 3.1.5 等价性定理、收敛阶等价性定理、收敛阶 定理定理 向量序

15、列向量序列 收敛到向量收敛到向量 的的 充分必要条件是存在某种向量范数充分必要条件是存在某种向量范数 使得使得 定义定义 对于收敛的向量序列，如果满足对于收敛的向量序列，如果满足 这里这里c为为收敛常数收敛常数，称该向量，称该向量p阶收敛阶收敛.按范数收敛按范数收敛目录下页返回上页结束 3.1.5 收敛速度收敛速度 小结小结 收敛阶用来刻画和比较收敛速度的快慢收敛阶用来刻画和比较收敛速度的快慢p越大收敛速度越快越大收敛速度越快.当当p1时称为线性收敛；时称为线性收敛；当当p大于大于1 1时称为超线性收敛；时称为超线性收敛；当当p2时为平方收敛（二次收敛）；时为平方收敛（二次收敛）；收敛阶相同的

16、算法说明收敛速度快慢基本相当，收敛阶相同的算法说明收敛速度快慢基本相当，更进一步的比较需考察收敛常数更进一步的比较需考察收敛常数c，c小的收敛小的收敛 速度更快一点速度更快一点.目录下页返回上页结束例例 比较下列数列的收敛速度比较下列数列的收敛速度解解 三个数列都会收敛到三个数列都会收敛到 0,但速度不同但速度不同目录下页返回上页结束线形收敛线形收敛,而而 二次收敛二次收敛,因此因此 收敛最快收敛最快,比比 的收敛常数小的收敛常数小,因此收敛稍快因此收敛稍快.目录下页返回上页结束 我们知道，通常给算法提供的输入数据会有我们知道，通常给算法提供的输入数据会有误差，计算机在运算过程中还会有新的误差

17、误差，计算机在运算过程中还会有新的误差产生产生.需要回答的一个问题是：需要回答的一个问题是：当原始数据有小的误差时，算法计算出的当原始数据有小的误差时，算法计算出的 结果是否也是有小扰动，而不是大的变化结果是否也是有小扰动，而不是大的变化.这就是算法的这就是算法的稳定性问题稳定性问题.3.2 误差和数值算法的稳定性误差和数值算法的稳定性 目录下页返回上页结束 3.2.1 误差的产生误差的产生 模型误差；模型误差；模型建立时因舍去次要矛盾而模型建立时因舍去次要矛盾而产生的误差产生的误差.观测误差；观测误差；模型中包含一些参数是通过仪模型中包含一些参数是通过仪表观测得到的，观测过程中带来的误差表观

18、测得到的，观测过程中带来的误差.截断误差；截断误差；算法必须在有限步内执行结束，算法必须在有限步内执行结束，将无穷过程截断为有限过程时产生的误差将无穷过程截断为有限过程时产生的误差.舍入误差；舍入误差；由于计算机表示的数据字长有限由于计算机表示的数据字长有限无法准确表示所有实数，由此产生误差无法准确表示所有实数，由此产生误差.目录下页返回上页结束 3.2.2 浮点数系及溢出浮点数系及溢出 浮点数系浮点数系是计算机常用的实数表示系统，一个是计算机常用的实数表示系统，一个浮点数的表示由正负号、有限小数形式的尾数、浮点数的表示由正负号、有限小数形式的尾数、以及确定小数点位置的阶码三部分组成以及确定小

19、数点位置的阶码三部分组成.0100000001100000000000000000000阶数s尾数t上溢界：上溢界：计计算机能表示的最大数算机能表示的最大数.下溢界：下溢界：计计算机能表示的最小数算机能表示的最小数3232位位=23=23位尾数位尾数+7+7位阶数位阶数+1+1位阶数符号位位阶数符号位+1+1位尾数符号位位尾数符号位目录下页返回上页结束 3.2.3 初值误差的传播初值误差的传播 由于误差传播研究困难，经常研究某种假设下由于误差传播研究困难，经常研究某种假设下误差的传播规律误差的传播规律.如如初值误差传播初值误差传播是在每一步是在每一步都准确计算的假设下，即不考虑截断误差和运都准

20、确计算的假设下，即不考虑截断误差和运算进一步引入的舍入误差，研究误差传播规律算进一步引入的舍入误差，研究误差传播规律.例、例、对函数对函数 用用 近似近似 则则 目录下页返回上页结束 3.2.4 数值稳定性数值稳定性 数值稳定的数值稳定的,否则称其为数值不稳定否则称其为数值不稳定.舍入误差分析是非常繁杂困难的舍入误差分析是非常繁杂困难的,而舍入误差而舍入误差不可避免不可避免,运算量又相当大运算量又相当大,为此为此,人们提出人们提出了了 数值稳定性数值稳定性 这一概念对舍入误差是否影响这一概念对舍入误差是否影响产生可靠的结果进行定性分析产生可靠的结果进行定性分析.定义定义 一个算法一个算法,如果

21、在运算过程中舍入误差在如果在运算过程中舍入误差在一定条件下能够得到控制一定条件下能够得到控制,或者舍入误差的或者舍入误差的增增长不影响产生可靠的结果长不影响产生可靠的结果,则称该算法是则称该算法是目录下页返回上页结束 例例 计算积分序列计算积分序列 ，由于，由于解法解法1 向前迭代向前迭代 可以采用迭代的解法求解可以采用迭代的解法求解.计算初值计算初值 建立迭代格式建立迭代格式 目录下页返回上页结束解法解法2 向后迭代向后迭代 利用上面不等式计算初值利用上面不等式计算初值 建立迭代格式建立迭代格式 目录下页返回上页结束严重失真严重失真目录下页返回上页结束的显著性分析的显著性分析.注注 算法的稳

22、定性不同于建立模型过程中因素算法的稳定性不同于建立模型过程中因素小结小结 向前迭代算法是一个稳定性不好的算法向前迭代算法是一个稳定性不好的算法.的舍入误差传播到的舍入误差传播到 时增大时增大5倍，如此进行，倍，如此进行，传播到传播到 时将增大时将增大 倍倍.向后迭代算法是一个稳定的算法向后迭代算法是一个稳定的算法.虽然初始值虽然初始值 精度不高精度不高,但每计算一步但每计算一步,舍入误差会减小舍入误差会减小 为原来的五分之一为原来的五分之一,取得了很好的计算效果取得了很好的计算效果.目录下页返回上页结束四、数值算法设计注意事项四、数值算法设计注意事项对于一个数值型算法除了其正确性（如收敛性），

23、对于一个数值型算法除了其正确性（如收敛性），研究其效率（如收敛速度）研究其效率（如收敛速度）,鲁棒性（如稳定性）鲁棒性（如稳定性）是很重要的，同时程序设计或实现时如下几个是很重要的，同时程序设计或实现时如下几个问题也不可忽视：问题也不可忽视：4.1 减少计算次数减少计算次数 4.2 避免相近数相减避免相近数相减 4.3 避免大数吃小数避免大数吃小数 4.4 避免很小的数做分母，防止溢出出现避免很小的数做分母，防止溢出出现 4.5 正确使用实数相等的比较正确使用实数相等的比较 目录下页返回上页结束 4.1 减少计算次数减少计算次数 设计算法时，好的算法能有效减少运算时间，设计算法时，好的算法能有

24、效减少运算时间，减小误差的积累减小误差的积累.对计算机而言，乘除法花费对计算机而言，乘除法花费 机时大大多于加减法，因此数值型算法以减机时大大多于加减法，因此数值型算法以减少少乘除法运算次数为主乘除法运算次数为主.例例 一般多项式求值问题一般多项式求值问题秦九韶算法秦九韶算法目录下页返回上页结束 4.2 避免相近数相减避免相近数相减 两个相近数相减会快速消减有效数字的位数两个相近数相减会快速消减有效数字的位数.例例 和和 都有都有5位有效数字，但是位有效数字，但是 只有只有1位有效位有效数字数字.注、注、通过改变算法可以避免这种现象通过改变算法可以避免这种现象.例例 已知已知解法解法1解法解法

25、2 1位有效位有效数字数字4位有效位有效数字数字目录下页返回上页结束一些避免相近数相减算法一些避免相近数相减算法 目录下页返回上页结束 4.3 避免大数吃小数避免大数吃小数 定义定义 在计算机做加法时，两加数的指数在计算机做加法时，两加数的指数先向大指数对齐，再将浮点部分相加，如先向大指数对齐，再将浮点部分相加，如两个数指数相差太大，就会出现小数无法两个数指数相差太大，就会出现小数无法加进去的现象加进去的现象.例例 、用单精度计算用单精度计算 的根的根解法解法1 求根公式求根公式 解法解法2 根与系数关系根与系数关系错误错误目录下页返回上页结束 4.4 其他注意事项其他注意事项 避免很小的数做

26、分母，防止溢出错误避免很小的数做分母，防止溢出错误正确使用实数相等比较算法正确使用实数相等比较算法在判断两个实数是否相等时，不应写成在判断两个实数是否相等时，不应写成而是先按精度需要设定一个很小的数而是先按精度需要设定一个很小的数 ，然后判断两数差的绝对值是否小于然后判断两数差的绝对值是否小于 目录下页返回上页结束五、算法的评价五、算法的评价同一问题可用不同算法解决，在分析了算法的同一问题可用不同算法解决，在分析了算法的可靠性之后，就需要对其效率进行分析可靠性之后，就需要对其效率进行分析.复杂度复杂度来考虑来考虑.一个算法的效率评价主要从一个算法的效率评价主要从时间复杂度时间复杂度和和空间空间

27、注、注、进行算法分析和评价的目的在于选择合适进行算法分析和评价的目的在于选择合适的算法和改进算法的算法和改进算法.目录下页返回上页结束 5.1 时间复杂度定义时间复杂度定义 某算法的时间开销某算法的时间开销理论分析理论分析大多不可行大多不可行计算机实测计算机实测可行但不必要可行但不必要比较算法时，只需要知道那种花费的时间多比较算法时，只需要知道那种花费的时间多,那种花费的时间少那种花费的时间少.并且时间花费和算法中语并且时间花费和算法中语句的执行次数成正比句的执行次数成正比.目录下页返回上页结束 5.1 时间复杂度定义时间复杂度定义 定义定义一个算法中的语句执行次数称为算法一个算法中的语句执行

28、次数称为算法时间频度是算法需要完成多少工作的度量时间频度是算法需要完成多少工作的度量.时间频度时间频度,记为记为 ,其中其中 是问题的规模是问题的规模.定义定义 算法时间频度是问题规模算法时间频度是问题规模 的函数的函数 则称则称 是是 的同数量级函数，记作的同数量级函数，记作称称 为算法的为算法的渐进时间复杂度渐进时间复杂度，简称，简称 时间复杂度时间复杂度.目录下页返回上页结束 5.2 问题的规模问题的规模 定义定义 将标识问题类中不同问题大小的参数将标识问题类中不同问题大小的参数定义定义为为问题的规模问题的规模.时所需存储空间的度量，时所需存储空间的度量，涉及到除原始数据涉及到除原始数据

29、外所需要额外增加的存储空间外所需要额外增加的存储空间.定义定义 空间复杂度空间复杂度是对算法在计算机内执行是对算法在计算机内执行 例例 向量向量 和和的内积的内积 解解 问题的规模为问题的规模为 ，空间复杂度为，空间复杂度为 .目录下页返回上页结束 例例 时间频度随规模变化分析时间频度随规模变化分析解解 算法算法 和和 的时间复杂度都是的时间复杂度都是 ,但但渐进常数渐进常数 ，意味着当问题规模意味着当问题规模 较大时，较大时，花费的时间基本上是花费的时间基本上是 的的3/4.3/4.目录下页返回上页结束注注 按数量级递增排列的时间复杂度有按数量级递增排列的时间复杂度有:随着问题规模随着问题规

30、模n的不断增大，上述时间复杂度的不断增大，上述时间复杂度不断增大，算法的执行效率越低不断增大，算法的执行效率越低.常数阶常数阶线性阶线性阶线性对数阶线性对数阶平方阶平方阶立方阶立方阶指数阶指数阶阶乘阶阶乘阶:目录下页返回上页结束n102030log10n0.000 001 0秒 0.000001 3秒 0.000001 5秒n0.000 01秒0.000 02秒0.000 03秒n20.000 1秒0.000 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.4

31、E16世纪 例例 给定给定n n，执行给定时间复杂度的算法耗时比较，执行给定时间复杂度的算法耗时比较目录下页返回上页结束 5.3 时间复杂度分析时间复杂度分析 考虑算法的渐进时间复杂度，即随着问题规模考虑算法的渐进时间复杂度，即随着问题规模 的增大时间频度的变化趋势的增大时间频度的变化趋势.注注 通常时间耗费是问题规模的单调增加函数，通常时间耗费是问题规模的单调增加函数，因而算法中的一些与问题规模无关的语句执行因而算法中的一些与问题规模无关的语句执行 时间可以不予考虑，因为该语句的频度是时间可以不予考虑，因为该语句的频度是 .注注 由于编译系统对循环语句中循环次数的控由于编译系统对循环语句中循

32、环次数的控制在编译时已经计算好，分析时可以不予考虑制在编译时已经计算好，分析时可以不予考虑.当对渐进常数的大小不关心，仅考虑其渐进阶当对渐进常数的大小不关心，仅考虑其渐进阶 数时，只需分析循环中某一个语句的执行频度数时，只需分析循环中某一个语句的执行频度.目录下页返回上页结束 例例1 计算两个向量点乘积的算法复杂度计算两个向量点乘积的算法复杂度.向量向量 和和 输入参数输入参数:问题规模问题规模 ,输出参数输出参数:点积点积addadd 算法伪代码算法伪代码:add=0；For i=1:nadd=add+x(i)*y(i)end i1nn+1全部统计的算法复杂度全部统计的算法复杂度 ,忽略循环

33、外忽略循环外语语句的算法复杂度为句的算法复杂度为 .目录下页返回上页结束 例例2 计算一个向量和两个矩阵乘积计算一个向量和两个矩阵乘积.向量向量 输入参数输入参数:问题规模问题规模 ,矩阵矩阵 输出参数输出参数:For i=1:n y(i)=0 z(i)=0 for j=1:n y(i)=y(i)+x(j)*a(i,j)z(i)=z(i)+x(j)*b(i,j)end j end inn 算法伪代码算法伪代码:算法复杂度算法复杂度目录下页返回上页结束 例例3 计算向量分量正弦值的最大值计算向量分量正弦值的最大值.向量向量 输入参数输入参数:问题规模问题规模 ,输出参数输出参数:最大值最大值ma

34、xmax 算法伪代码算法伪代码:算法复杂度算法复杂度 max=sin(x(1)for i=2:n t=sin(x(i)if tmax max=t endif end i1n-1n-1n-13n-2目录下页返回上页结束分析并不是算法分析的全部内容分析并不是算法分析的全部内容，它仅考虑了它仅考虑了 注注 例例2 2循环结构中有两条执行语句循环结构中有两条执行语句,如果只考如果只考 虑一条语句虑一条语句,算法复杂度为算法复杂度为 ,可见与总可见与总 时间复杂度同阶时间复杂度同阶,但渐进常数不同但渐进常数不同,说明数量级说明数量级 数量级最高项的级数量级最高项的级.注注 例例3 3选择结构中的语句只有在判断条件成立选择结构中的语句只有在判断条件成立 的时候才被执行的时候才被执行,我们考虑了最坏的一种情形我们考虑了最坏的一种情形,即每次都会被执行即每次都会被执行,这样分析出来的复杂度是这样分析出来的复杂度是 该问题类的一个上界该问题类的一个上界,被称为被称为最坏时间复杂度最坏时间复杂度.目录下页返回上页结束再见目录下页返回上页结束