数学建模简明教程市公开课一等奖百校联赛特等奖课件.pptx

数学建模简明教程国家精品课程国家精品课程第1页第八章第八章 算法基础算法基础一、一、算法概念算法概念二、数值型算法结构惯用思想二、数值型算法结构惯用思想三、数值算法可靠性三、数值算法可靠性 四、数值型算法设计注意事项四、数值型算法设计注意事项 五、五、算法评价算法评价目录下页返回上页结束第2页 1.1 数学建模竞赛过程数学建模竞赛过程 1.3 算法分类算法分类 1.4 算法评价算法评价 1.2 算法概念算法概念 一、算法概念一、算法概念目录下页返回上页结束第3页 1.1 数学建模竞赛过程数学建模竞赛过程 (1)提出问题：提出问题：命题人（某个领域教授）提出命题人（某个领域教授）提出 (2)分析问题：分析问题：参赛人首先读题，分析问题，依参赛人首先读题，分析问题，依(3)建立模型：建立模型：辨析问题中主要矛盾和次要矛辨析问题中主要矛盾和次要矛 (4)模型求解：模型求解：研究解存在性与惟一性，寻找研究解存在性与惟一性，寻找 目录下页返回上页结束实际问题实际问题；照自己了解准确阐述问题照自己了解准确阐述问题；间约束关系，进而得到完备数学模型；间约束关系，进而得到完备数学模型；理论、工具和方法，建立起问题中不一样量之理论、工具和方法，建立起问题中不一样量之盾，盾，并在合理假设条件下，利用各种数学并在合理假设条件下，利用各种数学求解方法，利用解对模型正确性进行评价求解方法，利用解对模型正确性进行评价.第4页 1.2 算法概念算法概念 定义定义 串行串行算法算法就是求解一个问题类无二义性就是求解一个问题类无二义性定义定义 原始可改变原始可改变有限操作对象有限操作对象就是有限输入就是有限输入注注 对给定输入数据，算法运行后得到数据对给定输入数据，算法运行后得到数据有穷过程，这里过程明确无歧义描述由有限有穷过程，这里过程明确无歧义描述由有限操作（算术、逻辑、字符运算和读写操作等）及操作（算术、逻辑、字符运算和读写操作等）及有限操作对象合成按一定次序执行有限序列有限操作对象合成按一定次序执行有限序列.数据，它全部可能允许改变组成求解数据，它全部可能允许改变组成求解问题类问题类.结果也是有限，结果也是有限，这么能够把算法看成有限输入这么能够把算法看成有限输入数据和有限输出结果之间对应关系数据和有限输出结果之间对应关系.目录下页返回上页结束第5页 1.3 算法分类算法分类 定义定义 依据对象不一样能够将算法分为依据对象不一样能够将算法分为数值型数值型目录下页返回上页结束算法算法和和非数值型算法非数值型算法.将以浮点算术运算为主将以浮点算术运算为主算法称为算法称为数值型算法数值型算法，非数值型算法非数值型算法普通普通包含线性表、栈、队列和串、树、图，排序、包含线性表、栈、队列和串、树、图，排序、查找等数据处理方面算法查找等数据处理方面算法.第6页 1.4 算法评价算法评价 优劣优劣才是有价值才是有价值.(1)算法可靠性评价算法可靠性评价 数值型算法：数值型算法：收敛性、稳定性、误差预计；收敛性、稳定性、误差预计；非数值型算法：强调对于整体问题类算法非数值型算法：强调对于整体问题类算法计算结果正确性计算结果正确性.(2)算法优劣评价算法优劣评价时间复杂度，空间复杂度，逻辑复杂度时间复杂度，空间复杂度，逻辑复杂度.注注 算法在确保可靠大前提下再评价其算法在确保可靠大前提下再评价其目录下页返回上页结束第7页二、结构数值型算法惯用思想二、结构数值型算法惯用思想了解数值型算法结构惯用基本思想，有利于了解数值型算法结构惯用基本思想，有利于针对自己研究详细问题提出有效可靠算法针对自己研究详细问题提出有效可靠算法.2.1 迭代思想迭代思想 2.2 直与曲思想直与曲思想 2.3 分段处理思想分段处理思想 2.4 修正思想修正思想 2.5 组合思想组合思想 2.6 自适应思想自适应思想 惯用基本思想：惯用基本思想：目录下页返回上页结束第8页 2.1 迭代思想迭代思想 非线性方程非线性方程 等价变形等价变形迭代格式迭代格式 产生迭代序列产生迭代序列假如假如则能够得到方程解则能够得到方程解.线性方程组线性方程组等价变形等价变形迭代格式迭代格式产生迭代向量序列产生迭代向量序列假如假如则可得到方程组解则可得到方程组解.目录下页返回上页结束第9页 2.2 直与曲思想直与曲思想 大多数曲线就一小范围来看大致能够看成是大多数曲线就一小范围来看大致能够看成是直线直线.非线性方程非线性方程 根可视为函数根可视为函数 与与 轴交点轴交点.在交点附近能够用在交点附近能够用 直线代替曲线直线代替曲线 ，对应地用直线与，对应地用直线与 x*Oyx 轴交点轴交点 代替曲线与代替曲线与 轴交点轴交点 .牛顿迭代法牛顿迭代法目录下页返回上页结束第10页例例 求解常微分方程初值问题求解常微分方程初值问题欧拉折线法欧拉折线法 经典以折线段近似曲线经典以折线段近似曲线.xyy(x)xnxn+1PnPn+1目录下页返回上页结束第11页 2.3 分段处理思想分段处理思想 已知一组采样点已知一组采样点 值，求非采样点处值，求非采样点处 函数值一个方法就是插值法函数值一个方法就是插值法.当当 较大时较大时,假如直接采取高次插值假如直接采取高次插值一是计算量大一是计算量大;二是高次插值不确保收敛，也不稳定二是高次插值不确保收敛，也不稳定.采取采取分段处理思想分段处理思想就能很好处理该问题就能很好处理该问题,即采取分段低次插值，既能确保稳定，又即采取分段低次插值，既能确保稳定，又收敛，计算量还小收敛，计算量还小.目录下页返回上页结束第12页 2.4 修正思想修正思想 记记 为线性方程组为线性方程组 一个近似，普通一个近似，普通说来残差说来残差 不等于零向量，对之不等于零向量，对之 进行修正得到更加好近似进行修正得到更加好近似 式中矩式中矩阵阵是由是由对对角元素角元素组组成矩成矩阵阵 逐一超松弛逐一超松弛迭代法迭代法注注 此方法采取就是给粗糙解向量一个此方法采取就是给粗糙解向量一个修正量修正量，以得到更加好解近似以得到更加好解近似.目录下页返回上页结束第13页 2.5 组合思想组合思想 对精度较低解近似进行组合，以期望得到对精度较低解近似进行组合，以期望得到近似精度高解近似近似精度高解近似.例例 龙贝格求积算法龙贝格求积算法.计算积分计算积分 将区间将区间 等分等分 个子个子区间区间,采取复化梯形公式得到近似值为采取复化梯形公式得到近似值为目录下页返回上页结束第14页 2.6 自适应思想自适应思想 自适应在算法结构中是非常主要思想，它在自适应在算法结构中是非常主要思想，它在结构算法时也同时兼顾了局部特征结构算法时也同时兼顾了局部特征.小小步长，改变平坦地方，步长较大一些步长，改变平坦地方，步长较大一些.例例 当使用复化梯形公式计算积分时，在函数当使用复化梯形公式计算积分时，在函数值改变较大地方使用较多节点，即使用较值改变较大地方使用较多节点，即使用较xyxyf(x)f(x)自适应自适应非自适应非自适应目录下页返回上页结束第15页三、数值算法可靠性三、数值算法可靠性 本节介绍算法可靠性三个方面：本节介绍算法可靠性三个方面：(1)算法收敛性算法收敛性：研究当运行时间趋于无限研究当运行时间趋于无限长时，算法解是否趋于真实解，即截断长时，算法解是否趋于真实解，即截断误差是否趋于零误差是否趋于零.(2)算法稳定性算法稳定性：就是当原始数据有小误就是当原始数据有小误差时，算法计算出结果是否也有小扰动，差时，算法计算出结果是否也有小扰动，而不是很大改变而不是很大改变.(3)误差预计误差预计：其其用途是设计循环终止条件，用途是设计循环终止条件，让数值解满足给定精度要求让数值解满足给定精度要求.目录下页返回上页结束第16页 3.1 近似解序列收敛性近似解序列收敛性 迭代迭代是结构数值问题算法基本思想之一，是结构数值问题算法基本思想之一，迭代得到问题解一个近似序列迭代得到问题解一个近似序列 ，假如假如 ，且，且 就是原问题解，就是原问题解，则称该迭代算法收敛到问题解则称该迭代算法收敛到问题解.多变量问题迭代算法，产生近似解序列多变量问题迭代算法，产生近似解序列是向量序列是向量序列 ，目录下页返回上页结束第17页 3.1.1 向量序列收敛定义向量序列收敛定义 定义定义 如存在向量如存在向量 使向量序使向量序列列 各分量组成数列收敛到向量各分量组成数列收敛到向量对应分量，即对应分量，即 称称向量序列向量序列 收敛到向量收敛到向量 .注注 上述收敛被称为按分量收敛，此定义即使上述收敛被称为按分量收敛，此定义即使直观，但不便于理论分析，所以引入向量按范直观，但不便于理论分析，所以引入向量按范数收敛定义数收敛定义.目录下页返回上页结束第18页 3.1.2 范数概念范数概念 定义定义 定义在定义在 上实值函数上实值函数 ，假如满足，假如满足1)非负性，即非负性，即2)齐次性，即齐次性，即3)三角不等式，即三角不等式，即则称函数则称函数 是该向量空间上一个是该向量空间上一个范数范数.注注 范数概念是对距离一个抽象和推广范数概念是对距离一个抽象和推广.目录下页返回上页结束第19页 3.1.3 惯用向量范数惯用向量范数 对于向量对于向量 ，惯用范数有，惯用范数有 例例 计算向量计算向量 各种范数各种范数 解解目录下页返回上页结束第20页 3.1.4 惯用矩阵范数惯用矩阵范数 定义定义 对于矩阵对于矩阵A，惯用范数有，惯用范数有 行和范数行和范数列和范数列和范数谱范数谱范数目录下页返回上页结束第21页 3.1.5 等价性定理、收敛阶等价性定理、收敛阶 定理定理 向量序列向量序列 收敛到向量收敛到向量 充分必要条件是存在某种向量范数充分必要条件是存在某种向量范数 使得使得 定义定义 对于收敛向量序列，假如满足对于收敛向量序列，假如满足 这里这里c为为收敛常数收敛常数，称该向量，称该向量p阶收敛阶收敛.按范数收敛按范数收敛目录下页返回上页结束第22页 3.1.5 收敛速度收敛速度 小结小结 收敛阶用来刻画和比较收敛速度快慢收敛阶用来刻画和比较收敛速度快慢p越大收敛速度越快越大收敛速度越快.当当p1时称为线性收敛；时称为线性收敛；当当p大于大于1 1时称为超线性收敛；时称为超线性收敛；当当p2时为平方收敛（二次收敛）；时为平方收敛（二次收敛）；收敛阶相同算法说明收敛速度快慢基本相当，收敛阶相同算法说明收敛速度快慢基本相当，更深入比较需考查收敛常数更深入比较需考查收敛常数c，c小收敛小收敛 速度更加快一点速度更加快一点.目录下页返回上页结束第23页例例 比较以下数列收敛速度比较以下数列收敛速度解解 三个数列都会收敛到三个数列都会收敛到 0,但速度不一样但速度不一样目录下页返回上页结束第24页线形收敛线形收敛,而而 二次收敛二次收敛,所以所以 收敛最快收敛最快,比比 收敛常数小收敛常数小,所以收敛稍快所以收敛稍快.目录下页返回上页结束第25页 我们知道，通常给算法提供输入数据会有我们知道，通常给算法提供输入数据会有误差，计算机在运算过程中还会有新误差误差，计算机在运算过程中还会有新误差产生产生.需要回答一个问题是：需要回答一个问题是：当原始数据有小误差时，算法计算出当原始数据有小误差时，算法计算出 结果是否也是有小扰动，而不是大改变结果是否也是有小扰动，而不是大改变.这就是算法这就是算法稳定性问题稳定性问题.3.2 误差和数值算法稳定性误差和数值算法稳定性 目录下页返回上页结束第26页 3.2.1 误差产生误差产生 模型误差；模型误差；模型建立时因舍去次要矛盾而模型建立时因舍去次要矛盾而产生误差产生误差.观察误差；观察误差；模型中包含一些参数是经过仪模型中包含一些参数是经过仪表观察得到，观察过程中带来误差表观察得到，观察过程中带来误差.截断误差；截断误差；算法必须在有限步内执行结束，算法必须在有限步内执行结束，将无穷过程截断为有限过程时产生误差将无穷过程截断为有限过程时产生误差.舍入误差；舍入误差；因为计算机表示数据字长有限因为计算机表示数据字长有限无法准确表示全部实数，由此产生误差无法准确表示全部实数，由此产生误差.目录下页返回上页结束第27页 3.2.2 浮点数系及溢出浮点数系及溢出 浮点数系浮点数系是计算机惯用实数表示系统，一个是计算机惯用实数表示系统，一个浮点数表示由正负号、有限小数形式尾数、浮点数表示由正负号、有限小数形式尾数、以及确定小数点位置阶码三部分组成以及确定小数点位置阶码三部分组成.0100000001100000000000000000000阶数s尾数t上溢界：上溢界：计计算机能表示最大数算机能表示最大数.下溢界：下溢界：计计算机能表示最小数算机能表示最小数3232位位=23=23位尾数位尾数+7+7位阶数位阶数+1+1位阶数符号位位阶数符号位+1+1位尾数符号位位尾数符号位目录下页返回上页结束第28页 3.2.3 初值误差传输初值误差传输 因为误差传输研究困难，经常研究某种假设下因为误差传输研究困难，经常研究某种假设下误差传输规律误差传输规律.如如初值误差传输初值误差传输是在每一步是在每一步都准确计算假设下，即不考虑截断误差和运都准确计算假设下，即不考虑截断误差和运算深入引入舍入误差，研究误差传输规律算深入引入舍入误差，研究误差传输规律.例、例、对函数对函数 用用 近似近似 则则 目录下页返回上页结束第29页 3.2.4 数值稳定性数值稳定性 数值稳定数值稳定,不然称其为数值不稳定不然称其为数值不稳定.舍入误差分析是非常繁杂困难舍入误差分析是非常繁杂困难,而舍入误差而舍入误差不可防止不可防止,运算量又相当大运算量又相当大,为此为此,人们提出人们提出了了 数值稳定性数值稳定性 这一概念对舍入误差是否影响这一概念对舍入误差是否影响产生可靠结果进行定性分析产生可靠结果进行定性分析.定义定义 一个算法一个算法,假如在运算过程中舍入误差在假如在运算过程中舍入误差在一定条件下能够得到控制一定条件下能够得到控制,或者舍入误差或者舍入误差增加不影响产生可靠结果,则称该算法是目录下页返回上页结束第30页 例例 计算积分序列计算积分序列 ，因为，因为解法解法1 向前迭代向前迭代 能够采取迭代解法求解能够采取迭代解法求解.计算初值计算初值 建立迭代格式建立迭代格式 目录下页返回上页结束第31页解法解法2 向后迭代向后迭代 利用上面不等式计算初值利用上面不等式计算初值 建立迭代格式建立迭代格式 目录下页返回上页结束第32页严重失真严重失真目录下页返回上页结束第33页显著性分析显著性分析.注注 算法稳定性不一样于建立模型过程中原因算法稳定性不一样于建立模型过程中原因小结小结 向前迭代算法是一个稳定性不好算法向前迭代算法是一个稳定性不好算法.舍入误差传输到舍入误差传输到 时增大时增大5倍，如此进行，倍，如此进行，传输到传输到 时将增大时将增大 倍倍.向后迭代算法是一个稳定算法向后迭代算法是一个稳定算法.即使初始值即使初始值 精度不高精度不高,但每计算一步但每计算一步,舍入误差会减小舍入误差会减小 为原来五分之一为原来五分之一,取得了很好计算效果取得了很好计算效果.目录下页返回上页结束第34页四、数值算法设计注意事项四、数值算法设计注意事项对于一个数值型算法除了其正确性（如收敛性），对于一个数值型算法除了其正确性（如收敛性），研究其效率（如收敛速度）研究其效率（如收敛速度）,鲁棒性（如稳定性）鲁棒性（如稳定性）是很主要，同时程序设计或实现时以下几个是很主要，同时程序设计或实现时以下几个问题也不可忽略：问题也不可忽略：4.1 降低计算次数降低计算次数 4.2 防止相近数相减防止相近数相减 4.3 防止大数吃小数防止大数吃小数 4.4 防止很小数做分母，预防溢出出现防止很小数做分母，预防溢出出现 4.5 正确使用实数相等比较正确使用实数相等比较 目录下页返回上页结束第35页 4.1 降低计算次数降低计算次数 设计算法时，好算法能有效降低运算时间，设计算法时，好算法能有效降低运算时间，减小误差积累减小误差积累.对计算机而言，乘除法花费对计算机而言，乘除法花费 机时大大多于加减法，所以数值型算法以减机时大大多于加减法，所以数值型算法以减少少乘除法运算次数为主乘除法运算次数为主.例例 普通多项式求值问题普通多项式求值问题秦九韶算法秦九韶算法目录下页返回上页结束第36页 4.2 防止相近数相减防止相近数相减 两个相近数相减会快速消减有效数字位数两个相近数相减会快速消减有效数字位数.例例 和和 都有都有5位有效数字，不过位有效数字，不过 只有只有1位有效位有效数字数字.注、注、经过改变算法能够防止这种现象经过改变算法能够防止这种现象.例例 已知已知解法解法1解法解法2 1位有效位有效数字数字4位有效位有效数字数字目录下页返回上页结束第37页一些防止相近数相减算法一些防止相近数相减算法 目录下页返回上页结束第38页 4.3 防止大数吃小数防止大数吃小数 定义定义 在计算机做加法时，两加数指数在计算机做加法时，两加数指数先向大指数对齐，再将浮点部分相加，如先向大指数对齐，再将浮点部分相加，如两个数指数相差太大，就会出现小数无法两个数指数相差太大，就会出现小数无法加进去现象加进去现象.例例 、用单精度计算用单精度计算 根根解法解法1 求根公式求根公式 解法解法2 根与系数关系根与系数关系错误错误目录下页返回上页结束第39页 4.4 其它注意事项其它注意事项 防止很小数做分母，预防溢犯错误防止很小数做分母，预防溢犯错误正确使用实数相等比较算法正确使用实数相等比较算法在判断两个实数是否相等时，不应写成在判断两个实数是否相等时，不应写成而是先按精度需要设定一个很小数而是先按精度需要设定一个很小数 ，然后判断两数差绝对值是否小于然后判断两数差绝对值是否小于 目录下页返回上页结束第40页五、算法评价五、算法评价同一问题可用不一样算法处理，在分析了算法同一问题可用不一样算法处理，在分析了算法可靠性之后，就需要对其效率进行分析可靠性之后，就需要对其效率进行分析.复杂度复杂度来考虑来考虑.一个算法效率评价主要从一个算法效率评价主要从时间复杂度时间复杂度和和空间空间注、注、进行算法分析和评价目标在于选择适当进行算法分析和评价目标在于选择适当算法和改进算法算法和改进算法.目录下页返回上页结束第41页 5.1 时间复杂度定义时间复杂度定义 某算法时间开销某算法时间开销理论分析理论分析大多不可行大多不可行计算机实测计算机实测可行但无须要可行但无须要比较算法时，只需要知道那种花费时间多比较算法时，只需要知道那种花费时间多,那种花费时间少那种花费时间少.而且时间花费和算法中语而且时间花费和算法中语句执行次数成正比句执行次数成正比.目录下页返回上页结束第42页 5.1 时间复杂度定义时间复杂度定义 定义定义一个算法中语句执行次数称为算法一个算法中语句执行次数称为算法时间频度是算法需要完成多少工作度量时间频度是算法需要完成多少工作度量.时间频度时间频度,记为记为 ,其中其中 是问题规模是问题规模.定义定义 算法时间频度是问题规模算法时间频度是问题规模 函数函数 则称则称 是是 同数量级函数，记作同数量级函数，记作称称 为算法为算法渐进时间复杂度渐进时间复杂度，简称，简称 时间复杂度时间复杂度.目录下页返回上页结束第43页 5.2 问题规模问题规模 定义定义 将标识问题类中不一样问题大小参数将标识问题类中不一样问题大小参数定义定义为为问题规模问题规模.时所需存放空间度量，时所需存放空间度量，包括到除原始数据包括到除原始数据外所需要额外增加存放空间外所需要额外增加存放空间.定义定义 空间复杂度空间复杂度是对算法在计算机内执行是对算法在计算机内执行 例例 向量向量 和和内积内积 解解 问题规模为问题规模为 ，空间复杂度为，空间复杂度为 .目录下页返回上页结束第44页 例例 时间频度随规模改变分析时间频度随规模改变分析解解 算法算法 和和 时间复杂度都是时间复杂度都是 ,但但渐进常数渐进常数 ，意味着当问题规模意味着当问题规模 较大时，较大时，花费时间基本上是花费时间基本上是 3/4.3/4.目录下页返回上页结束第45页注注 按数量级递增排列时间复杂度有按数量级递增排列时间复杂度有:伴随问题规模伴随问题规模n不停增大，上述时间复杂度不停增大，上述时间复杂度不停增大，算法执行效率越低不停增大，算法执行效率越低.常数阶常数阶线性阶线性阶线性对数阶线性对数阶平方阶平方阶立方阶立方阶指数阶指数阶阶乘阶阶乘阶:目录下页返回上页结束第46页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.4E16世纪 例例 给定给定n n，执行给定时间复杂度算法耗时比较，执行给定时间复杂度算法耗时比较目录下页返回上页结束第47页 5.3 时间复杂度分析时间复杂度分析 考虑算法渐进时间复杂度，即伴随问题规模考虑算法渐进时间复杂度，即伴随问题规模 增大时间频度改变趋势增大时间频度改变趋势.注注 通常时间花费是问题规模单调增加函数，通常时间花费是问题规模单调增加函数，因而算法中一些与问题规模无关语句执行因而算法中一些与问题规模无关语句执行 时间能够不予考虑，因为该语句频度是时间能够不予考虑，因为该语句频度是 .注注 因为编译系统对循环语句中循环次数控因为编译系统对循环语句中循环次数控制在编译时已经计算好，分析时能够不予考虑制在编译时已经计算好，分析时能够不予考虑.当对渐进常数大小不关心，仅考虑其渐进阶当对渐进常数大小不关心，仅考虑其渐进阶 数时，只需分析循环中某一个语句执行频度数时，只需分析循环中某一个语句执行频度.目录下页返回上页结束第48页 例例1 计算两个向量点乘积算法复杂度计算两个向量点乘积算法复杂度.向量向量 和和 输入参数输入参数:问题规模问题规模 ,输出参数输出参数:点积点积addadd 算法伪代码算法伪代码:add=0；For i=1:nadd=add+x(i)*y(i)end i1nn+1全部统计算法复杂度全部统计算法复杂度 ,忽略循环外忽略循环外语语句算法复杂度为句算法复杂度为 .目录下页返回上页结束第49页 例例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 算法伪代码算法伪代码:算法复杂度算法复杂度目录下页返回上页结束第50页 例例3 计算向量分量正弦值最大值计算向量分量正弦值最大值.向量向量 输入参数输入参数:问题规模问题规模 ,输出参数输出参数:最大值最大值maxmax 算法伪代码算法伪代码:算法复杂度算法复杂度 max=sin(x(1)for i=2:n t=sin(x(i)if tmax max=t endif end i1n-1n-1n-13n-2目录下页返回上页结束第51页分析并不是算法分析全部内容分析并不是算法分析全部内容，它仅考虑了它仅考虑了 注注 例例2 2循环结构中有两条执行语句循环结构中有两条执行语句,假如只考假如只考 虑一条语句虑一条语句,算法复杂度为算法复杂度为 ,可见与总可见与总 时间复杂度同阶时间复杂度同阶,但渐进常数不一样但渐进常数不一样,说明数量级说明数量级 数量级最高项级数量级最高项级.注注 例例3 3选择结构中语句只有在判断条件成立选择结构中语句只有在判断条件成立 时候才被执行时候才被执行,我们考虑了最坏一个情形我们考虑了最坏一个情形,即每次都会被执行即每次都会被执行,这么分析出来复杂度是这么分析出来复杂度是 该问题类一个上界该问题类一个上界,被称为被称为最坏时间复杂度最坏时间复杂度.目录下页返回上页结束第52页再见目录下页返回上页结束第53页