01软件基础徐士良第一章 算法_40学时.ppt

第一章算法 计算机软件技术基础 2020 1 21 计算机软件技术基础第一章算法 2 1 1集合的基本概念 1 集合的基本概念 所谓集合 就是指若干个或无穷多个具有相同属性的元 元素 的集体 集合的两个表示方法 列举法 将此集合中的元素全部列举出来 或者列出若干项但能根据规律可知其所有的元素 这就是列举法 性质叙述法 用性质叙述法表示一个集合是将集合中的元素所具有的属性出来 2020 1 21 计算机软件技术基础第一章算法 3 1 1算法的基本概念 2 集合的基本运算 两个集合的并两个集合的交两个集合的差 2020 1 21 计算机软件技术基础第一章算法 4 1 1算法的基本概念 2 集合的基本性质 结合律分配律 2020 1 21 计算机软件技术基础第一章算法 5 1 1算法的基本概念 3 映射设A B是两个非空集合 根据一定的法则 对于每个 在B中都有唯一确定的元素y与之对应 称f是定义在A上而在B中取值的映射 记为f A B 并将x与y的关系记为y f x 其中 x称为自变元 y称为f作用下x的像 2020 1 21 计算机软件技术基础第一章算法 6 1 1算法的基本概念 2020 1 21 计算机软件技术基础第一章算法 7 第一章算法 1 1算法的基本概念1 2算法设计基本方法1 3算法的复杂度分析 什么是算法 算法的基本特征 1 列举法 2 递推法 3 递归法 4 减半递推法 5 回溯法 算法的时间复杂度 2020 1 21 计算机软件技术基础第一章算法 8 1 1算法的基本概念 用计算机解决一个实际问题 首先要进行程序设计 通常 程序设计主要包括两个方面 行为特性的设计 要求将解决实际问题的每个细节准确地加以定义 并且还应当将全部解题过程完整地描述出来 这一过程即是算法的设计 结构特性的设计 指确定适合的数据结构 2020 1 21 计算机软件技术基础第一章算法 9 1 1算法的概念 定义 算法 是指解题方案的准确而完整的描述 算法可解 对于一个问题 如果可以通过一个计算机程序 在有限的存储空间内运行有限长的时间而得到正确的结果 程序与算法的区别 程序可以作为算法一种描述 但程序通常还需考虑很多与方法和分析无关的细节问题 因为在编写程序时要受到计算机系统运行环境的限制 结论 通常 程序设计不可能优于算法的设计 2020 1 21 计算机软件技术基础第一章算法 10 1 1 1算法的基本特征 能 可 行性 effectiveness 算法中的每一个步骤必须能够实现 算法执行的结果要能够达到预期的目的 例如 三个量的和 如果采用不同的运算顺序 就会得到不同的结果 数据存储的实际范围 2020 1 21 计算机软件技术基础第一章算法 11 确定性 definiteness 算法中每一个步骤都必须是有明确定义的 不允许有模棱两可的解释 也不允许有多义性 反映了算法与数学公式的明显差别 针对某种特殊情况 数学公式是正确的 但按此数学公式设计的计算过程可能会使计算机系统无所适从 因为没有考虑异常情况的出现 举例 输入一个x 若x比1大很多 则输出数字1 否则输出数字0 2020 1 21 计算机软件技术基础第一章算法 12 有穷性 finiteness 算法必须能在有限的时间内做完 即算法必须能在执行有限个步骤之后终止 举例 一个数的无穷级数表示只是一个计算公式 而根据精度要求确定的计算过程才是有穷的算法 另一种定义 合理的执行时间 2020 1 21 计算机软件技术基础第一章算法 13 补充 无穷级数 无穷级数是研究有次序的可数无穷个数或者函数的和的收敛性及和的数值的方法 举例 假定有一个无穷数列 u1 u2 u3 un 其前n项的和为 Sn u1 u2 u3 un由此得出另一个新无穷数列 S1 S2 S3 Sn 当n无限增加时 Sn趋向一个极限 如果极限存在 这个无穷数列就叫做是收敛的无穷级数 如果极限不存在 这个数列就是发散的 只有收敛的无穷级数存在一个和S S u1 u2 u3 un 2020 1 21 计算机软件技术基础第一章算法 14 拥有足够的情报一个算法是否有效还取决于为算法所提供的情报是否足够 通常 算法中的各种运算总是要施加到各个运算对象上 而这些运算对象又可能具有某种初始状态 这是算法执行的起点或是依据 因此 一个算法执行的结果总是与输入的初始数据有关 不同的输入会有不同的输出 当提供的情报不够时 算法并不是有效的 2020 1 21 计算机软件技术基础第一章算法 15 结论 算法是一组严谨地定义运算顺序的规则 并且每一个规则都是有效的 且是明确的 此顺序将在有限的次数下终止 算法是对特定问题求解步骤的一种描述 它是指令的有限序列 2020 1 21 计算机软件技术基础第一章算法 16 1 1 2算法的基本要素 算法通常由两种基本要素组成 一是对数据对象的运算和操作 二是算法的控制结构 算法中对数据的运算和操作 算术运算 加 减 乘 除 整除 取余等运算 逻辑运算 与 或 非 等运算 关系运算 大于 小于 等于 不等于 等运算 数据传输 赋值 输入 输出等操作 2020 1 21 计算机软件技术基础第一章算法 17 算法的控制结构定义 算法中各操作之间的执行顺序 描述算法的工具 传统流程图 N S结构化流程图 算法描述语言 三种基本控制结构 顺序 选择 循环 2020 1 21 计算机软件技术基础第一章算法 18 1 2算法设计的基本方法 计算机解题的过程实际上是在实施某种算法 这种算法通常称为计算机算法 与人工处理的算法不同 举例 2020 1 21 计算机软件技术基础第一章算法 19 算法设计的基本方法 人工处理的步骤 找出被积函数f x 的源函数F x 利用牛顿 莱布尼兹公式计算 计算机处理方式 采用数值积分法 根据实际被积函数的类型以及精度要求选择相应的算法 2020 1 21 计算机软件技术基础第一章算法 20 列举法 基本思想 根据提出的问题 列举所有可能的情况 并用问题中给定的条件检验哪些是需要的 哪些是不需要的 列举法常用于解决 是否存在 或 有多少种可能 等类型的问题 例如求解不定方程的问题 特点 算法比较简单 但当列举的可能情况较多时 执行列举算法的工作量将会很大 2020 1 21 计算机软件技术基础第一章算法 21 举例 百鸡百钱问题 例1 1 设每只母鸡值3元 每只公鸡值2元 两只小鸡值1元 现要用100元钱买100只鸡 设计买鸡方案 百鸡百钱问题 假设买母鸡i只 公鸡j只 小鸡k只 2020 1 21 计算机软件技术基础第一章算法 22 最粗略的列举算法如下 算法 求解百鸡百钱问题 fori 0to100doforj 0to100dofork 0to100do m i j kn 3i 2j 0 5kif m 100 and n 100 thenoutputi j k return 2020 1 21 计算机软件技术基础第一章算法 23 1013 F 2020 1 21 计算机软件技术基础第一章算法 24 改进算法 求解百鸡百钱问题 fori 0to33doforj 0to50 1 5ido k 100 i jif 3i 2j 0 5k 100 thenoutputi j k return总循环次数为 运行结果如下 0230680525700820721115741410761757820080 2020 1 21 计算机软件技术基础第一章算法 25 递推 基本思想 从已知的初始条件出发 逐次推出所要求的各中间结果和最后结果 补充举例 计算下列定积分 递推算法在数值计算中极为常见 但对于数值型的递推算法必须要注意数值计算的稳定性问题 2020 1 21 计算机软件技术基础第一章算法 26 对上式稍作分析 可以发现相邻两个积分之间存在以下关系 从而得到递推公式 2020 1 21 计算机软件技术基础第一章算法 27 利用牛顿 莱布尼兹公式可以计算出积分I0的值 从而得到21个积分的递推算法如下 2020 1 21 计算机软件技术基础第一章算法 28 表1 1第一种递推公式得到的结果 2020 1 21 计算机软件技术基础第一章算法 29 实际上 根据关系式 还可以得到另一个递推公式 2020 1 21 计算机软件技术基础第一章算法 30 如果要使用递推公式 1 5 时 需要确定初始值I20 有如下不等式 可以得到 最后可得 当n 21时 有 由于很接近 因此可用它们的平均值作为I20的近似值 即 2020 1 21 计算机软件技术基础第一章算法 31 根据之前的推论 可以得到第二种21个积分的递推算法 假定初始值 情报 的误差为 2020 1 21 计算机软件技术基础第一章算法 32 表1 2第二种递推公式得到的结果 递推算法在数值计算中极为常见 但对于数值型的递推算法必须要注意数值计算的稳定性问题 2020 1 21 计算机软件技术基础第一章算法 33 递归 基本思想 将一个复杂的问题归结为若干个较简单的问题 然后将这些较简单的每一个问题再归结为更简单的问题 这个过程可以一直做下去 直到最简单的问题为止 补充举例 求解Hanoi塔问题 2020 1 21 计算机软件技术基础第一章算法 34 补充举例 求解Hanoi 汉诺 塔问题 设有三个塔座分别为X Y Z 现有n个直径各不相同的圆盘 且按直径从小到大用自然数编号为1 2 n 开始时 此n个圆盘依下大上小的顺序放在塔盘X上 先要根据下列原则将X塔座上的这n个圆盘移动到Z塔座上 每次只允许移动一个圆盘 从一个塔座到另一个塔座 移动时可用Y塔座作为中间塔座 在移动过程中 任何一个塔座上均不允许出现大压小的情况发生 2020 1 21 计算机软件技术基础第一章算法 35 图示Hanoi塔问题 每次只允许移动一个圆盘 从一个塔座到另一个塔座 移动时可用Y塔座作为中间塔座 在移动过程中 任何一个塔座上均不允许出现大压小的情况发生 2020 1 21 计算机软件技术基础第一章算法 36 三阶Hanoi塔问题 分析 起始塔座X上有三个圆盘 所以该问题被称为三阶Hanoi塔问题 需要完成 Hanoi 3 X Y Z 其中 参数1表示一共需要移动几个圆盘 参数2表示起始塔座 参数3表示中间塔座 参数4表示目的塔座 2020 1 21 计算机软件技术基础第一章算法 37 三阶Hanoi塔问题 分析 完成Hanoi 3 X Y Z 的工作可以分解成如下三个步骤 Hanoi 2 X Z Y MOVE X 3 Z 和Hanoi 2 Y X Z 需要先完成 Hanoi 2 X Z Y 该工作又可分解成 Hanoi 1 X Y Z MOVE X 2 Y Hanoi 1 Z X Y 完成Hanoi 1 X Y Z 工作等价于MOVE X 1 Z 2020 1 21 计算机软件技术基础第一章算法 38 三阶Hanoi塔问题 分析 完成Hanoi 3 X Y Z 的工作可以分解成如下三个步骤 Hanoi 2 X Z Y MOVE X 3 Z 和Hanoi 2 Y X Z 需要先完成 Hanoi 2 X Z Y 该工作又可分解成 Hanoi 1 X Y Z MOVE X 2 Y Hanoi 1 Z X Y 完成MOVE X 2 Y 2020 1 21 计算机软件技术基础第一章算法 39 三阶Hanoi塔问题 分析 完成Hanoi 3 X Y Z 的工作可以分解成如下三个步骤 Hanoi 2 X Z Y MOVE X 3 Z 和Hanoi 2 Y X Z 需要先完成 Hanoi 2 X Z Y 该工作又可分解成 Hanoi 1 X Y Z MOVE X 2 Y Hanoi 1 Z X Y 完成Hanoi 1 Z X Y 工作等价于MOVE Z 1 Y Hanoi 2 X Z Y 完成 2020 1 21 计算机软件技术基础第一章算法 40 三阶Hanoi塔问题 分析 完成Hanoi 3 X Y Z 的工作可以分解成如下三个步骤 Hanoi 2 X Z Y MOVE X 3 Z 和Hanoi 2 Y X Z 完成 MOVE X 3 Z 接下来需要完成 Hanoi 2 Y X Z 2020 1 21 计算机软件技术基础第一章算法 41 三阶Hanoi塔问题 分析 完成Hanoi 3 X Y Z 的工作可以分解成如下三个步骤 Hanoi 2 X Z Y MOVE X 3 Z 和Hanoi 2 Y X Z 最后完成 Hanoi 2 Y X Z 该工作又可分解成 Hanoi 1 Y Z X MOVE Y 2 Z Hanoi 1 X Y Z 完成Hanoi 1 Y Z X 其工作等价于MOVE Y 1 X 2020 1 21 计算机软件技术基础第一章算法 42 三阶Hanoi塔问题 分析 完成Hanoi 3 X Y Z 的工作可以分解成如下三个步骤 Hanoi 2 X Z Y MOVE X 3 Z 和Hanoi 2 Y X Z 最后完成 Hanoi 2 Y X Z 该工作又可分解成 Hanoi 1 Y Z X MOVE Y 2 Z Hanoi 1 X Y Z 完成MOVE Y 2 Z 2020 1 21 计算机软件技术基础第一章算法 43 三阶Hanoi塔问题 分析 完成Hanoi 3 X Y Z 的工作可以分解成如下三个步骤 Hanoi 2 X Z Y MOVE X 3 Z 和Hanoi 2 Y X Z 最后完成 Hanoi 2 Y X Z 该工作又可分解成 Hanoi 1 Y Z X MOVE Y 2 Z Hanoi 1 X Y Z 完成Hanoi 1 X Y Z 其工作等价于MOVE X 1 Z Hanoi 2 Y X Z 完成 Hanoi 3 X Y Z 完成 2020 1 21 计算机软件技术基础第一章算法 44 总结 三阶Hanoi塔问题 将一个复杂的问题 三阶Hanoi塔问题 归结为若干个较简单的问题 二阶Hanoi塔问题 然后将这些较简单的每一个问题 二阶Hanoi塔问题 再归结为更简单的问题 直到最简单的问题 一阶Hanoi塔问题 为止 2020 1 21 计算机软件技术基础第一章算法 45 再分析 n阶Hanoi塔问题 求解的步骤 如果n 1 则可直接将这一个圆盘移动到目的柱上 过程结束 如果n 1 则进行步骤2 设法将起始柱的上面n 1个圆盘 编号1到n 1 按移动原则移动到中间柱上 将起始柱上的最后一个圆盘 编号为n 移到目的柱上 设法将中间柱上的n 1圆盘按移动原则移到目的柱上 2020 1 21 计算机软件技术基础第一章算法 46 步骤2与步骤4实际上还是Hanoi塔问题 只不过其规模小一些而已 如果最原始的问题为n阶Hanoi塔问题 且表示为Hanoi n X Y Z 则步骤2与步骤4为n 1阶Hanoi塔问题分别表示为 Hanoi n 1 X Z Y Hanoi n 1 Y X Z 其中第一个参数表示问题的阶数 第二 三 四个参数分别表示起始柱 中间柱与目的柱 将X塔座上的n号圆盘移到Z塔座上Move X n Z 2020 1 21 计算机软件技术基础第一章算法 47 补充举例之算法 求解n阶Hanoi塔问题 Hanoi n X Y Z IFn 1THENmove X 1 Z ELSE Hanoi n 1 X Z Y move X n Z Hanoi n 1 Y X Z RETURN 函数在执行过程中调用自身的方法叫递归调用 2020 1 21 计算机软件技术基础第一章算法 48 另一个简单的例子 例1 2 编写一个过程 对于输入的参数n 依次打印输出自然数1到n 非递归算法 PROCEDUREWRT n FORk 1TOnDOOUTPUTkRETURN 2020 1 21 计算机软件技术基础第一章算法 49 输出自然数1到n的递归算法 PROCEDUREWRT1 n IF n 0 THEN WRT1 n 1 OUTPUTn RETURN 递归的边界 123 2020 1 21 计算机软件技术基础第一章算法 50 总结 一个典型的递归算法 自己调用自己 直接递归 如果一个算法P显式地调用自己 间接递归 如果算法P调用另一个算法Q 而算法Q又调用算法P 递归算法与递推算法的区别 两者的实现方法是大不一样的 递推是从初始条件出发 逐次推出所需求的结果 而递归则是从算法本身达到递归边界 2020 1 21 计算机软件技术基础第一章算法 51 减半递推 所谓 减半 是指将问题的规模减半 而问题的性质不变 所谓 递推 是指重复 减半 的过程 将实际问题的规模逐渐减少 可明显地降低解决问题的复杂程度 这种方法称为分治法 即对问题分而治之 工程上常用的分治法是减半递推技术 这个技术在快速算法的研究中有很重要的使用价值 2020 1 21 计算机软件技术基础第一章算法 52 举例 例1 3 二分法求方程f x 在 a b 的根设方程f x 0在区间 a b 内有且只有一个实根 则函数f x 在区间的两个端点处的函数值必异号 即 2020 1 21 计算机软件技术基础第一章算法 53 首先取给定区间的中点c a b 2 然后判断f c 是否为0 若f c 0 则说明c即为所求的根 求解过程结束 如果f c 0 则根据以下原则将原区间减半 若f a f c 0 则取原区间的前半部分 若f b f c 0 则取原区间的后半部分 最后判断减半后的区间长度是否已经很小 若 a b 则过程结束 取 a b 2为根的近似值 若 a b 则重复上述的减半过程 2020 1 21 计算机软件技术基础第一章算法 54 算法1 3二分法求方程的根输入 根所在区间 a b 精度要求输出 满足精度要求的根的近似值cf0 f a WHILE b a DO c a b 2 f1 f c IFf1 0THEN OUTPUTcRETURN IFf0 f1 0THENa cELSEb c c a b 2OUTPUTcRETURN 2020 1 21 计算机软件技术基础第一章算法 55 总结 对于有些实际问题 可以设计出直观的减半递推算法 经过逐次的减半递推 直接得到所需求的结果 如例1 3 二分法求方程的根 对于另外一些问题 根据减半递推技术设计出的算法是递归算法 在执行过程中只能靠算法本身到达递归边界 如例子 两个n阶矩阵相乘的快速方法就是递归算法 斯特拉森 Strassen 算法 2020 1 21 计算机软件技术基础第一章算法 56 回溯法 通过对问题的分析 找出一个解决问题的线索 然后沿着这个线索逐步试探 对于每一步的试探 若试探成功 就得到问题的解 若试探失败 就逐步回退 换别的路线再进行试探 例1 4求解皇后问题 2020 1 21 计算机软件技术基础第一章算法 57 例1 4求解皇后问题 由n2个方块排成n行n列的正方形称为 n元棋盘 如果两个皇后位于棋盘上的同一行或同一列或同一对角线上 则称它们为互相攻击 现要求找使n元棋盘上的n个皇后互不攻击的所有布局 分析 假设棋盘上的每一行放置一个皇后 分别用自然数进行编号为1 2 n 首先 将问题归结为在n元棋盘的每一行上安置一个皇后 并假设第i个皇后被安置在第i行上 定义一个长度为n的一维数组q 其中每一个元素q i i 1 2 n 用于在安置皇后过程中随时记录第i行上的皇后所在列号 2020 1 21 计算机软件技术基础第一章算法 58 此时 在安置每一行上的皇后时 只需考虑每两个皇后不能在同一列或者同一对角线上即可 容易验证 第i行上的皇后和第j行上的皇后正好在同一列上的充要条件为 q i q j 0正好在某一对角线上的充要条件为 q i q j i j 0在初始时 将每一行的皇后均放在第一列 即初始状态为 q i 1 i 1 2 3 n 2020 1 21 计算机软件技术基础第一章算法 59 然后从第一行 即i 1 开始进行以下过程 设前i 1行行的皇后已经布局好 即它们互不攻击 现考虑安排第i行上的皇后位置 使之与前i 1行上的皇后也互不攻击 为了实现这一点 需要从第i行皇后的当前位置开始向右搜索 2020 1 21 计算机软件技术基础第一章算法 60 若q i n 则需检查第i行皇后与前i 1行的皇后是否互不攻击 若无攻击 则考虑安排下一行皇后的位置 若有攻击 则将第i行皇后右移一个位置 重新进行这个过程 若q i n 则说明在前i 1行皇后的当前布局下 第i行皇后无法安置 此时 将第i行皇后重新放在第一列 且回退一行 考虑第i 1行皇后与前i 2行皇后均互不攻击的下一个位置 在这种情况下 如果已经退到第0行 n元棋盘不存在第0行 则过程结束 若当前安置好的皇后是在最后一行 即第n行 则说明已找到了n个皇后互不攻击的一个布局 将这个布局打印输出 然后将第n行的皇后右移一个位置 重新进行这个过程 以便进一步寻找出另外的布局 2020 1 21 计算机软件技术基础第一章算法 61 举例 5阶皇后问题 初始状态 五粒皇后棋子最初均被放置在每一行的第1列 即 数组q 5 中的五个元素均取初值1 2020 1 21 计算机软件技术基础第一章算法 62 举例 5阶皇后问题 皇后1 前面没有其它皇后 所以保留其初始值1 表示该皇后棋子被放置在第1行 1号皇后 第1列 q 1 1 2020 1 21 计算机软件技术基础第一章算法 63 举例 5阶皇后问题 皇后2 前面有皇后1 从第1列开始寻找和前面的所有皇后棋子均不相互攻击的位置 第一个合适的位置在第3列 q 2 3 2020 1 21 计算机软件技术基础第一章算法 64 举例 5阶皇后问题 皇后3 前面有皇后1和皇后2 寻找到第一个合适的位置 与皇后1 2均不相互攻击 为第2列 q 3 2 2020 1 21 计算机软件技术基础第一章算法 65 举例 5阶皇后问题 皇后4 前面有皇后1 2和3 寻找到第一个合适的位置为第5列 q 4 5 2020 1 21 计算机软件技术基础第一章算法 66 举例 5阶皇后问题 皇后5 前面有皇后1 4 寻找到第一个合适的位置为第4列 q 5 4 找到一个布局 找到一个5元棋盘上的5个皇后互不攻击布局 即这5粒棋子相互均不在同一行 同一列和同一对角线上 2020 1 21 计算机软件技术基础第一章算法 67 举例 5阶皇后问题 重新开始查找新布局 从上一布局最后一粒皇后棋子开始 将皇后5右移动一格 q 5 5 原来的位置 新的位置 2020 1 21 计算机软件技术基础第一章算法 68 举例 5阶皇后问题 发现问题 皇后5找不到一个合适的新位置 所以说明前四个皇后棋子的位置不合适 所以问题回溯到皇后4的重新找位上 其皇后5回到第1列 2020 1 21 计算机软件技术基础第一章算法 69 举例 5阶皇后问题 又发现新问题 皇后4也找不到一个合适的新位置 所以说明前三个皇后棋子的位置不合适 所以问题回溯到皇后3的重新找位上 其皇后4回到第1列 2020 1 21 计算机软件技术基础第一章算法 70 举例 5阶皇后问题 重找新布局之皇后3 通过皇后3不断后移 又发现了第4列是一个合适的位置 q 3 4 此时皇后3与皇后1 2均不相互攻击 原来的位置 新的位置 2020 1 21 计算机软件技术基础第一章算法 71 举例 5阶皇后问题 重找新布局之皇后4 皇后4右移动 发现新的合适位置第2列 即q 4 2 2020 1 21 计算机软件技术基础第一章算法 72 举例 5阶皇后问题 重找新布局之皇后5 皇后5右移动 发现只能放在第5列 但显然不合适 所以重新回溯到皇后4寻找 同时皇后5回到第1列 2020 1 21 计算机软件技术基础第一章算法 73 举例 5阶皇后问题 重找新布局之回溯皇后4 皇后4右移动 发现新位置第5列 q 4 5 2020 1 21 计算机软件技术基础第一章算法 74 举例 5阶皇后问题 重找新布局之皇后5 皇后5右移动 发现新位置第2列 q 5 2 此时找到第二个布局 又找到一个布局 找到一个5元棋盘上的5个皇后互不攻击布局 即这5粒棋子相互均不在同一行 同一列和同一对角线上 2020 1 21 计算机软件技术基础第一章算法 75 总结 综合以上过程 可以形象地概括成一句话 向前走 碰壁回头 这种方法也称为深度优先搜索DFS DepthFirstSearch 技术 2020 1 21 计算机软件技术基础第一章算法 76 算法1 4求解皇后问题 输入 n 输出 n个皇后互不攻击的各种布局 即数组元素q i i 1 2 n FORi 1TOnDOq i 1i 1loop IF q i n THEN k 1WHILE k i and q k q i q k q i k i 0 DOk k 1IF k i THENq i q i 1 2020 1 21 计算机软件技术基础第一章算法 77 ELSE i i 1 考虑下一行皇后的位置IF i n THEN OUTPUTq i i 1 2 n q n q n 1 重新考虑新的棋盘布局i n 2020 1 21 计算机软件技术基础第一章算法 78 ELSE 前i 1行的棋盘布局不能保证第i行皇后 可以找到合适的位置 q i 1i i 1IF i 1 THENRETURNq i q i 1 GOTOloopRETURN 2020 1 21 计算机软件技术基础第一章算法 79 1 3算法的复杂度分析 算法的复杂度主要是指时间复杂度与空间复杂度 1 3 1算法的时间复杂度定义 执行这个算法的计算工作量 即算法的时间代价 面临的问题 如何分析一个算法的工作量 简单的解决办法 执行算法所需的时间作为算法工作量的度量 2020 1 21 计算机软件技术基础第一章算法 80 另一种对于时间复杂度的度量 用算法程序中所执行的的指令条数或语句条数来度量算法的工作量 缺点 程序中各种指令或者语句的执行速度是极不相同的 而且这种方法又很大程度上取决于所使用的程序设计语言以及编制程序者的水平和风格 所以这种方法也是不可取的 2020 1 21 计算机软件技术基础第一章算法 81 结论 为了能够客观地反映出一个算法的效率 度量算法工作量的方法必须与所使用的计算机 程序设计语言以及编制程序者无关 应该与算法实现过程中的许多细节 包括循环控制变量的计算 数组下标的计算 设置数据结构指针等 簿记 bookkeeping 无关 用算法在执行过程中所需基本运算的执行次数来度量算法的工作量 2020 1 21 计算机软件技术基础第一章算法 82 如何选择基本运算 应该遵循的两个原则 算法执行的运算总次数与基本运算的次数大体上要成正比 基本运算以外的其它运算其运算量可以忽略 举例 在一维数组中顺序查找值为x的元素 可以选取 x和数组元素的比较 作为基本运算 在两个实矩阵相乘的算法中 可以选取 两个实数的乘法 作为基本运算 2020 1 21 计算机软件技术基础第一章算法 83 举例 顺序查找 一维数组L 10 该形式被称为是长度为10的线性表的顺序存储 顺序实现 要求 在该数组中分别查找并分别输出元素29和元素48的位置 如果该元素不在其中则输出 1 结果 查找成功 查找失败 L 10 元素29在数组L中查找成功 位置为6 顺序与数组L中的所有元素比较后得出查找失败的结论 输出结果 1 该算法的基本操作应为 两两元素的比较 2020 1 21 计算机软件技术基础第一章算法 84 举例 矩阵相乘 两个4阶的矩阵相乘 由于计算机在进行实数运算时 乘法运算的时间代价要远远高于加法运算的时间代价 该算法的基本操作应为 实数间的乘法运算 2020 1 21 计算机软件技术基础第一章算法 85 算法所执行的基本运算次数有时与问题的规模有关 举例 两个20阶矩阵相乘与两个10阶矩阵相乘 算法的工作量用算法所执行的基本运算次数来度量 而算法所执行的基本运算次数是问题规模n的函数 即f n 同时 一个算法的具体工作量 即对于一个固定的规模n 算法所执行的基本运算次数还可能与特定的输入有关 举例 在长度为n的一个维数组中查找值为x的元素 采用顺序查找法 2020 1 21 计算机软件技术基础第一章算法 86 两种分析算法工作量的方法 1 平均性态 AerageBehavior 当问题的规模为n时 算法执行的基本运算次数取决于某一特定的输入 可以用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量 设x为所有可能输入中某个特定输入 p x 是x出现的概率 即输入为x的概率 T x 是算法在输入为x时所执行的基本运算次数 则算法的平均性态 2020 1 21 计算机软件技术基础第一章算法 87 最坏情况复杂性 Worst CaseComplexity 含义 在规模为n时 算法所执行的基本运算的最大次数 2020 1 21 计算机软件技术基础第一章算法 88 举例说明 例1 5设L是包含n个元素的一维数组 对于指定的输入x 如果x在数组中 则顺序找到它第一次出现处的下标 如果x不在数组中 则以下标0作为查找结果 2020 1 21 计算机软件技术基础第一章算法 89 算法 顺序搜索法 SequentialSearch 输入 一维数组L 1 n 被查项x 输出 第一次使L j x的j 若x不在数组L中 则输出j 0 j 1WHILE j n and L j x DOj j 1IFj nTHENj 0OUTPUTjRETURN 2020 1 21 计算机软件技术基础第一章算法 90 1 平均性态分析 设被查项x在数组L中的概率为q 当输入的x为L i 时 算法所做的比较次数为 其中x L n 1 表示x不在数组L中的情况 再假设输入的x出现在数组中的每个位置上的可能性是一样的 即 2020 1 21 计算机软件技术基础第一章算法 91 于是有 2020 1 21 计算机软件技术基础第一章算法 92 2 最坏情况分析 最坏情况发生在当x是数组的最后一个元素或者x不在数组中的时候 这时有 即 在这两种情况下 要和数组中所有的元素进行比较 有关数量关系的计算 数量关系评价体现在时间 算法编程后在机器中所耗费的时间 数量关系评价体现在空间 算法编程后在机器中所占的存储量 1 关于算法执行时间 一个算法的执行时间大致上等于其所有语句执行时间的总和 对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积 2 语句频度 语句频度是指该语句在一个算法中重复执行的次数 例1 1两个n n阶矩阵相乘 该算法每一语句的语句频度为 for i 0 i n i nfor j 0 j n j n2 c i j 0 n2for k 0 k n k n3c i j c i j a i k b k j n3 3 算法的时间复杂度 对于算法分析 我们关心的是算法中语句总的执行次数T n 是关于问题规模n的函数 进而分析T n 随n的变化情况并确定T n 的数量级 OrderofMagnitude 在这里 我们用 O 来表示数量级 这样我们可以给出算法的时间复杂度概念 所谓算法的时间复杂度 即是算法的时间量度 记作 T n O f n 它表示随问题规模n的增大 算法的执行时间的增长率和f n 的增长率相同 称作算法的渐进时间复杂度 简称时间复杂度 一般情况下 随n的增大 T n 的增长较慢的算法为最优的算法 例如 在下列三段程序段中 给出原操作x x 1的时间复杂度分析 1 x x 1 其时间复杂度为O 1 我们称之为常量阶 2 for i 1 i n i x x 1 其时间复杂度为O n 我们称之为线性阶 3 for i 1 i n i for j 1 j n j x x 1 其时间复杂度为O n2 我们称之为平方阶 此外算法还能呈现的时间复杂度有对数阶O log2n 指数阶O 2n 等 4 数据结构中常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个 O 1 常数型O n 线性型O n2 平方型O n3 立方型O 2n 指数型O log2n 对数型O nlog2n 二维型 按时间复杂度由小到大递增排列成表1 3 当n充分大时 不同数量级的时间复杂度的形状如图1 6所示 表1 3与图1 6是同一问题的不同表示形式 一般情况下 随n的增大 T n 增长较慢的算法为最优的算法 从中我们应该选择使用多项式阶O nk 的算法 而避免使用指数阶的算法 2020 1 21 计算机软件技术基础第一章算法 98 补充 时间频度与时间复杂度 1 时间频度一个算法花费的时间与算法中语句的执行次数成正比例 哪个算法中语句执行次数多 它花费时间就多