计算机算法设计与分析.ppt

第一章绪论 计算机与软件学院 SchoolofComputerandSoftware NanjingUniversityofInformationScience Technology 第一章绪论 1 1算法的概念及其特性1 2衡量算法性能的标准1 3算法的时间和空间复杂度1 4算法分析1 5最优算法1 6高效算法的必要性 算法设计与分析 主要研究内容是 如何通过计算机将一个给定的输入高效地转化为所需要的输出 包括 算法设计算法分析 1 1算法的概念及其特性 算法 Algorithm 对特定问题求解步骤的一种描述 是指令的有限序列 一 算法的定义 算法的形式化定义 算法是一个四元组 Q I F 其中 Q是包含子集I和 的集合 表示计算的状态 I 分别表示计算的输入 输出集合 F表示计算的规则 它是一个由Q到它自身的函数 且具有自反性 即对于任何qQ 有F q q 二 算法的特性 算法的5个特性 输入 有零个或多个外部量作为算法的输入 输出 算法产生至少一个量作为输出 确定性 definiteness 组成算法的每条指令清晰 无歧义 有穷性 finiteness 算法中每条指令的执行次数有限 执行每条指令的时间也有限 可行性 effectiveness 算法描述的操作可以通过已经实现的基本操作执行有限次来实现 算法与程序的区别算法是解决问题的一种方法或一个过程 一个问题可以有多种算法 程序是用某种程序设计语言对算法的具体实现 主要区别在 有穷性 描述方法程序可以是无穷的 例如OS 而算法是有穷的 例 程序是用程序设计语言描述 在机器上可以执行 而算法还可以用框图 自然语言等多种方式描述 例如操作系统 是一个在无限循环中执行的程序 因而不是一个算法 操作系统的各种任务可看成是单独的问题 每一个问题由操作系统中的一个子程序通过特定的算法来实现 该子程序得到输出结果后便终止 描述算法可以有多种方式自然语言 流程图 伪语言等 三 算法的描述 表达算法的抽象机制 伪语言接近高级语言 易学 易掌握 使得设计出来的算法可读性好 可维护性强 可靠性高 伪语言算法易于转换为高级语言程序 算法书写注意点 1 算法说明 通常在算法头部之下以注释指明 算法功能 参数含义及输入输出属性 算法引用的全局变量或外部变量 其作用 初值及应满足的限制条件等 2 适当的注释 3 输入与输出 1 scanf printf 2 函数参数 3 全局变量 4 错误处理 1 函数返回状态 2 内部出错处理 5 算法结构与语句选用 1 分支 循环结构 if switch while for 2 尽量避免用 do do while while或 if if if 等结构 StatusListInsert Sq SqList ListInsert Sq 举例 顺序表插入操作算法描述 四 算法与数据结构 算法与数据结构的关系不了解施加于数据上的算法就无法决定如何构造数据 可以说算法是数据结构的灵魂 反之算法的结构和选择又常常在很大程度上依赖于数据结构 数据结构则是算法的基础 算法 数据结构 程序 1 2衡量算法性能的标准 1 正确性 correctness 执行结果应当满足功能要求 2 可读性 readability 为了人的阅读和交流 要求算法易于理解 便于分析 3 健壮性 robustness 输入非法数据也能适当地作出反应或进行处理 也称 鲁棒性 4 效率与低存储量 高效率 低存储我们这里主要讨论算法的时间和空间性能 并以此作为衡量算法性能的重要标准 而且我们主要侧重于时间方面 时间复杂度 TimeComplexity 算法的时间复杂度 在算法运行期间所花费的时间 通常用渐进形式表示例如 T n O n2 n2 n2 空间复杂度 SpaceComplexity 算法的空间复杂度 在算法运行期间所需要的辅助内存空间 auxiliaryspace orworkspace 通常用渐进形式表示例如 S n O n2 n2 n2 1 3算法的时间和空间复杂度 1 4算法分析 算法分析 对于算法的时间和空间复杂度进行定量分析 一 分析时间复杂度的基本步骤 Step1 计算出在算法运行期间基本运算执行的总频数 Step2 表示为渐近时间复杂度 asymptotictimecomplexity 二 渐近符号 1 定义 大 O 符号 增长阶上界 若存在两个正的常数c和n0 对于任意 n0 都有T n c f n 则称T n 的增长阶不超过f n 的增长阶 记为T n O f n 例 1 设f n 3n g n n 因对所有n 1 有3n 4n c 4 n0 1 所以有f n O g n 2 设f n n 10 g n n 因对所有n 1 有n 10 11n c 11 n0 1 所以有f n O g n 3 设f n 2n2 11n 10 g n n2 因对所有n 10 有2n2 11n 10 3n2 c 3 n0 10 所以有f n O g n 4 设f n n2 g n n3 因对所有n 1 有n2 n3 c 1 n0 1 所以有f n O g n 注意到 满足 O 符号定义的函数f n 并不是唯一的 所以有以下约定 一个函数增长阶的上界是该函数的所有上界中的最小者 忽略常数因子和低次项 例 百鸡问题 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 问鸡翁 母 雏各几何 a 公鸡只数 b 母鸡只数 c 小鸡只数 约束方程 a b c 1005a 3b c 3 100c 3 0 第一种解法 a b c的可能取值范围 0 100 对在此范围内的a b c的所有组合进行测试 凡是满足上述三个约束方程的组合 都是问题的解 第二种解法 公鸡只数 n 5 母鸡只数 n 3 小鸡只数 n a b 算法 改进的百鸡问题输入 所购买的三种鸡的总数目n输出 满足问题的解的数目k 公鸡 母鸡 小鸡的只数g m s 1 chicken problem intn int14 15 16 17 算法chicken problem的时间花费 取n0 28 对 有 令 c 13 并令 有 所以 含义 的增长最多象的增长那样快 称是的上界 运行时间的上界 O 2 大 符号 增长阶下界 定义若存在两个正的常数c和n0 对于任意n n0 都有T n c g n 则称T n 的增长阶不小于f n 的增长阶 记为T n g n 例 设T n 3n2 2n 求其增长阶的下界 因对所有n 1 有 T n 3n2 2n 3n2 c 3 n0 1 所以有T n n2 注意到 满足 符号定义的函数f n 并不是唯一的 所以有以下约定 一个函数增长阶的下界是该函数的所有下界中的最大者 忽略常数因子和低次项 例 百鸡问题chicken problem算法第10 11 12 13行 仅在条件成立时才执行 其执行次数未知 假定条件都不成立 这些语句一次也没有执行 所以该算法的执行时间至少为 当取 1时 存在常数 和函数 使得 所以 T n n2 含义 的增长至少象的增长那样快 表示一个解决问题的算法的时间下界 运行时间的下界 3 符号 增长阶相同 渐进的紧的界 定义若既有T n O f n 又有T n g n 则称函数T n 的增长阶等于f n 的增长阶 记为T n f n 例 T n 5n2 8n 1当n 1时 5n2 8n 1 5n2 8n n 5n2 9n 5n2 9n2 14n2 O n2 当n 1时 5n2 8n 1 5n2 n2 当n 1时 14n2 5n2 8n 1 5n2则 5n2 8n 1 n2 例 百鸡问题chicken problem算法 运行时间的上界是 下界是 这表明无论输入规模如何变化 该算法的运行时间都介于和之间 表明该算法运行时间的准确界是 含义 的增长与的增长有同样的阶 表明算法的运行时间有一个较准确的界 运行时间的准确界 定理设f g是两个函数 若r为 0的常数 则f n g n 证 设r c为 0的常数 由极限的定义可知 取为c 2 则必存在某个n0 当n n0时 总在c 2 3c 2之间 于是 对所有n n0时 f n 从而f n O g n 并且对所有n n0 有f n 从而f n g n 渐近符号的性质 1 和函数 对 也成立 O f n O g n O max f n g n O f n O g n O f n g n 2 传递性 对 也成立 f n O g n g n O h n f n O h n 3 乘积 对 也成立 O f n O g n O f n g n O cf n O f n 两个函数f g增长阶的比较定义了这两个函数之间的一个二元关系 具有的性质 性质O f n O g n O max f n g n 的证明 对于任意f1 n O f n 存在正常数c1和自然数n1 使得对所有n n1 有f1 n c1f n 类似地 对于任意g1 n O g n 存在正常数c2和自然数n2 使得对所有n n2 有g1 n c2g n 令c3 max c1 c2 n3 max n1 n2 h n max f n g n 则对所有的n n3 有f1 n g1 n c1f n c2g n c3f n c3g n c3 f n g n c32max f n g n 2c3h n O max f n g n 4 自反性f n f n f n O f n f n f n 5 对称性f n g n g n f n 6 反对称性f n O g n g n f n 增长阶的极限形式判别法 定理设f g是两个函数 则 1 c 0 f n 与g n 同阶 f n g n 2 c 0 f n 比g n 低阶 f n O g n 3 c f n 与g n 高阶 f n g n 三 算法时间复杂度的有关概念 最好时间复杂度 指算法对所有可能输入集的最小执行时间最坏时间复杂度 指算法对所有可能输入集的最大执行时间平均时间复杂度 指算法对所有可能输入集的执行时间的平均值 对于算法的时间复杂度 通常从分平均 最坏 最好几种情形来衡量 尤其是前两种 例 顺序查找算法以元素的比较作为基本操作 考虑成功检索的情况 最好情况下的时间复杂度 1 最坏情况下的时间复杂度 n 在等概率前提下 平均情况下的时间复杂度 n intsearch inta intn intkey for i 0 i n i if a i key returni return 1 四 算法分析中常见的复杂度函数 各种数量级的f n 五 算法渐近分析的步骤 统计基本操作次数 简化 得到统计结果 基本概念 渐近复杂度 O 平均时间复杂度 最坏时间复杂度 最好时间复杂度基本技术 常用求和公式递归方程求解 基本技术 根据循环统计基本操作次数用递归关系统计基本操作次数 统计基本操作次数的常用方法根据循环统计基本操作的次数利用递归关系求基本操作的次数 例 选择排序 voidsele sort intA intn for i 0 i n 1 i index i for j i 1 j n j if A j A index index j if index i temp A index A index A i A i temp T n n 1 n 1 2 1 n2 5 2 T1 n n T2 n 1 T3 n n 1 2 T4 n 1 例2 利用递归关系来基本操作的次数 求Fibonacci数列的第n项 该数列的定义为 F0 F1 1 Fi Fi 1 Fi 2 i 2 由这一数学定义自然地导出一个递归算法 intF intn if n 0 n 1 return1 elseif n 2 returnF n 1 F n 2 该算法的计算时间T n 满足递归方程 T n T n 1 T n 2 1 n 1 初始条件T 0 T 1 0 六 常用求和公式 1 算术级数 2 多项式级数 平方和级数 k方和级数 3 几何级数 4 算术 几何级数 也称递推方程 recurrenceequation 是自然数n上一个函数T n 它使用一个或多个小于n时的值的等式或不等式来描述 递推方程也称为递推关系或递推式 递推方程必须有一个初始条件 也称边界条件 七 解递归方程 2020 3 17 47 可编辑 例 逆序输出正整数的各位数 voidPrintDigit unsignedintn printf n 10 输出最后一位数dkif n 10 PrintDigit n 10 以逆序输出前k 1位数 时间分析设n d1d2 dk是k位数 当k 1时 只执行printf语句和if判定语句 当n至少是2位数 k 1 时 除了执行这两个操作外 还需执行递归函数调用PrintDigit n 10 n 10 是k 1位数 T k 2k 2 k 迭代法 展开法 将递归方程的的右端项通过迭代展开成级数 然后估计级数和的渐进阶 生成函数 母函数 法替换法先估计递归方程的显式解 再用数学归纳法证明 主方法若递归方程形如 T n aT n b f n 可根据f n 的不同情况使用主定理 常用方法 1 展开法 Recursivelyexpand 将递归方程展开直到方程右边不再含有未知函数T 而代之以一个级数 对这个级数求和即可得到方程的解 例 T n 2T n 2 5n2 设n 2k T 1 7解 由原方程可得T n 2 2T n 4 5 n 2 2T n 4 2T n 8 5 n 4 2 T n 2k 1 2T n 2k 5 n 2k 1 2代入原方程 得 10n2 3n 例 使用迭代法分析程序 算法 汉诺塔算法1voidHanoi intn charA charB charC 2 3if n 1 Move A C Move是一个抽象操作 表示将碟子从A移到C上4else 5Hanoi n 1 A C B 6Move A C 7Hanoi n 1 B A C 8 9 分析 函数Hanoi中两次调用自身 函数调用使用的实在参数均为n 1 函数Move所需时间具有常数界 1 可将其视为一个程序步 于是有 扩展并计算此递推式 T n 2T n 1 1 2 2T n 2 1 1 22T n 2 2 1 23T n 3 22 2 1 2n 1T 1 22 2 1 2n 1 22 2 1 2n 1 使用递归树 recursiontree 可以形象地看到递推式的迭代过程 例 T n 2T n 2 n的递归树 2 用生成函数 母函数 解递归函数 1 生成函数的定义定义 令是一个数列 构造如下的函数 该函数称为数列a0 a1 a2 的生成函数 例 函数是序列的生成函数 2 生成函数的性质 1 加法设是序列的生成函数 是序列的生成函数 则是序列的生成函数 2 移位设是序列的生成函数 则是序列的生成函数 3 乘法设是序列的生成函数 是序列的生成函数 则是序列的生成函数 其中 4 z变换设是序列的生成函数 则是序列的生成函数 当时 有 式1 则是序列1 1 1 的生成函数 特别地 有 所以 是序列的生成函数 若取数列为算法的时间复杂度函数 T n 则其生成函数为 f x T 0 T 1 x T n xn 如果能由T n 的递归方程求出T n 的生成函数 则其展开式第n项系数即为T n 3 用生成函数法求解递归方程 例汉诺塔 Hanoi 问题 递归关系式 式2 用作为系数 构造一个生成函数 令 根据式2 h n 2h n 1 1 由式1 得 所以 令 有 解得 所以 有 它是式中第项的系数 替换方法要求首先猜测递推式的解 然后用归纳法证明 例 使用替换方法分析程序Hanoi问题的时间 可以先对以下这些小的示例进行计算 T 3 7 23 1 T 4 15 24 1 T 5 31 25 1 T 6 63 26 1总结规律 猜测 T n 2n 1 n 1 3 替换法 证明 归纳法证明 1 当n 1时 h 1 1 结论成立 2 归纳法假设 当k n时 有h k 2k 1 3 那么 当k n时 h n 2h n 1 1 2 2n 1 1 1 2n 1 因此 对所有n 1 h n 2n 1 2n 4 主方法 主方法在递归算法分析中 常需求解如下形式的递推式 T n aT n c f n 式中 a 1和c 1是常数 f n 是一个渐近正函数 n c指 n c 或 n c 求解这类递推式的方法称为主方法 定理 设a b c为非负常数 其中n是c的幂 则其解是 主定理 例 T n 16T n 4 nT 1 1对照公式 a 16 c 4 b 1 符合情况 3 例 T n 2T n 2 n对照公式 a 2 c 2 b 1 符合情况 2 例 T n 3T n 4 n对照公式 a 3 c 4 b 1 符合情况 1 1 5最优算法 optimalalgorithm 一 问题的下界 定义一个问题的下界是解决该问题的任意算法所需要的最小时间复杂度 注 定义中的时间复杂度指最坏时间复杂度 首先对已知的解决该问题的算法进行分析 找出同类算法中共有的基本操作的最大集合 再证明这些基本操作 或其中的一些基本操作构成的子集 在最坏情况下对于该问题的解决是必不可少的 问题下界的确定 例 在一个无序数组中查找最大元的算法 输入 数组E 数组大小n 输出 最大元素max intfindMax int E intn intmax max E 0 Assumemax for index 1 index n index if max E index max E index returnmax 算法findMax的最好 最坏和平均时间复杂度都一样 为 n 查找无序数组最大元的所有算法的时间复杂度的下界是否是 n 分析 不失一般性 只考虑数组中各元素互不相同的情形 因此n元数组中最大元只有一个 对其余n 1个元素 要判定它不是最大元 至少要找到一个比它大的元素 因此需要至少一次比较 所以 为了找出最大元 任何算法至少需要n 1次比较 由此可确定查找最大元问题的算法复杂度下界为 n 定义如果一个算法的时间复杂度等于这个问题的下界 那么该算法是最优的 二 最优算法 例 算法findMax即为最优算法 例如 排序问题的计算时间下界为 nlogn 时间复杂度为O nlogn 的排序算法是最优算法 堆排序算法是最优算法 1 6高效算法的必要性 例 设算法A在输入规模为n时的计算时间为T n 3 2n 在计算机C1上执行该算法的算法是t秒 现有另一台计算机C2 其运行速度是C1的64倍 则在C2上用算法A在t秒内能解输入规模为多大的问题 若算法的计算时间改进为T n n2 其余条件不变 则在C2上用t秒内能解输入规模为多大的问题 解 设C2用算法A在t秒内能解n1规模的问题 则有 得n1 n 6 设C2用改进算法在t秒内能解n2规模的问题 则有 得n2 8n 不同时间复杂度下不同输入规模的算法运行时间 这里假定每一个操作时间是1ns n 纳秒 微秒ms 毫秒s 秒h 小时d 天y 年c 世纪 计算机速度提高10倍后 不同算法复杂度求解规模的扩大情况 FasterComputerorFasterAlgorithm 附录 基本数据结构复习 线性结构线性表栈队列串非线性结构树 二叉树图 a1 a2 ai 1 ai ai 1 an 一 线性表有关的概念 数据元素 表头 ai的直接前驱 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 表尾 n 0时称为空表 在数据元素的非空有限集中 1 存在唯一的一个被称为 第一个 的数据元素 开始结点 2 存在唯一的一个被称为 最后一个 的数据元素 终端结点 3 除第一个之外 每个数据元素均只有一个前驱 4 除最后一个之外 每个数据元素均只有一个后继 线性表的特点 线性表的顺序存储结构 Locate ai 1 Locate ai sizeof ElemType Locate ai Locate a1 sizeof ElemType i 1 单链表 用一组任意的存储单元存储线性表的各个数据元素 数据元素之间的关系通过保存直接后继元素的存储位置来表示 线性表的链式存储和实现 栈 是限制仅在线性表的一端进行插入和删除运算的线性表 栈顶 top 允许插入和删除的一端 栈底 bottom 不允许插入和删除的一端 空栈 表中没有元素 栈的特点 后进先出 LIFO 特殊的线性表 栈 定义 队列是只允许在一端删除 在另一端插入的线性表 队头 fro