《算法效率分析基础》PPT课件.ppt

算法设计与分析计算机与信息学院 2 使用教材 使用教材 作者 美 AnanyLevitin译者 潘彦出版社 清华大学丛书名 国外经典教材 计算机科学与技术 第2章算法效率分析基础 算法效率分析框架渐进符号和基本效率类型非递归算法效率分析递归算法效率分析 4 算法效率分析框架 算法效率分析框架本节将概要地描述一个分析算法效率的一般性框架 时间效率指出算法运行得有多快 空间效率关心算法需要的额外空间 目前 随着计算机硬件技术的飞速发展 空间效率已不是关心重点 因此 我们主要关心的是时间效率 输入规模的度量 问题规模 一个显而易见的事实 几乎所有的算法 对于更大规模输入都需要运行更长的时间 即算法耗费的时间随着输入规模的增大而增加 例如 1 更大的数组排序需要花费更多的运行时间 2 更大的矩阵相乘需要花费更多的运算时间 因此 采用一个以算法输入规模n为参数的函数 来研究算法效率就是非常合乎逻辑的 输入规模的选择问题 在大多数情况下 选择这样一个参数是非常直接的 例如 对于排序 查找以及其他大多数与列表相关的问题来讲 这个参数就是列表长度 对于n次多项式求值问题 这个参数是多项式次数或者系数个数 5 输入规模的选择 当然 有些情况下 怎样选择输入规模参数是有差别的 例如计算两个n阶矩阵的乘积 有两种度量输入规模的方法 第一种方法 选择矩阵的阶n 第二种方法 选择参与乘法运算的所有元素个数 第二种方法更具一般性 适用于非方阵 对于选择不同的输入规模 其算法效率在含义上有所差别 选择输入规模参数的合适量度 会受到算法操作细节的影响 例如 对于一个检查文字拼写的算法 如果算法要求对每个字符都要检查 那么应该用字符数作为输入规模度量 如果算法操作的是单词 那么选择单词数作为输入规模的度量 若算法与数字特性 数字的大小 相关 那么在度量它的输入规模时 计算机科学家倾向于选择数字的二进制位数作为输入规模的度量 6 时间效率的度量 运行时间的度量 接下来考虑运行时间的度量问题 我们为何不选择时间的标准度量单位 秒 毫秒等 来度量算法的运行时间呢 其理由如下 1 它依赖于特定计算机的运行速度 2 它依赖于实现算法的代码质量 程序员编程的水平问题 3 它依赖于编译器的好坏 编译成机器码的质量 即指令条数 4 它还依赖于一些其他问题如操作系统的调度策略等 鉴于此 希望找到一个不依赖于上述因素的时间度量 问 是否统计算法的每步操作执行次数来作为算法的时间效率度量呢 答 无此必要且较困难 一个算法中有许多操作 决定算法时间效率的是那些很耗费时间的操作步 因此只需关心这些操作即可评价一个算法时间效率 这些最关键的操作步称为基本操作 它们对算法执行时间的占用最大 基本操作即算法中最费时的操作 所以 用基本操作执行次数来作为时间效率的度量 7 基本操作的选取 基本操作的选取例 大多数排序算法是通过比较排序元素 键 来进行工作 因此它的基本操作应选为键的比较操作 即算法中键的比较次数 矩阵乘法 或多项式运算 需完成两种操作 乘法和加法 对多数机器而言 乘法比加法更耗费时间 所以选取乘法为基本操作 在定义了算法的输入规模n和基本操作后 我们就可以建立起一个算法时间效率的分析框架 对规模为n的算法 通过统计其基本操作的执行次数来度量算法的时间效率 时间耗费T为输入规模n的函数 分析框架的应用 设t为算法的一个基本操作在特定机器上的执行时间 C n 为该算法需执行的基本操作数 用下式来估计该算法在该机器上的运行时间 忽略了非基本操作执行时间 问 为什么用约等于符号 8 分析框架的应用例 分析框架的应用例 根据上式 我们可以回答以下问题 1若某算法运行在一台比现在机器快10倍的机器上 此算法运行多快 答 10倍 t增加10倍 C n 不变 2设 若输入规模翻倍 该算法运行时间如何变化 n不是太小如n 100 不考虑每个操作步在机器上具体的执行时间t 则时间耗费即为 时间耗费即为基本操作数 为输入规模n的函数 n的一次 二次函数分别称线性 二次增长率 2n称指数增长率 9 增长次数 增长率 增长次数 增长率 基本操作数 时间耗费 是输入规模n的函数 记为T n T n 随着n次数的增加而增加 函数值T n 增加快慢 决定于这个增长函数特性 也就是说 线性增长函数的函数值增加较慢 二次增长函数增加较快 指数增长函数最快 因此 我们最关心的就是函数的增长率 它决定了算法的时间耗费 效率 若输入规模n很小 无论是高效的算法还是低效的算法 时间耗费差距不明显 所以算法分析针对大规模输入 增长函数表 对于算法分析具有重要意义的函数值 近似值 10 算法效率算例 算法的最优 最差 平均效率前述已知 我们用输入规模n的函数T n 来度量算法的效率 若T n 随n增长快 则算法效率较差 若T n 随n增长较慢 则算法效率更好 这里 没考虑算法效率与特定输入的关系 诸多算法的效率不仅与规模有关 且与特定的输入有关 下面以顺序查找算法为例 名称 顺序查找 要求 在列表中查找一次给定项 查找键 该列表有n个元素 算法 从列表头开始 逐个比较列表中元素 直到发现匹配查找键的元素或者到达列表尾为止 没找到 分析 1 很明显 该算法的执行效率与查找键在列表中的位置有密切关系 2 若查找键位于表头 第一个元素 该算法只比较一次 最优效率3 若查找键位于表尾 最末元素 或不存在 该算法将比较n次 最差4 若查找键位于表中间 该算法比较次数不固定 平均效率 通过上述例子 引入最佳 最差和平均效率的概念 11 最优 最差效率 1最差效率 最为关注 当输入规模为n时 算法在最坏情况下的效率 此时 相对于其他规模为n的输入 该算法运行时间最长 最慢 最差效率的确定 原理上讲 首先对算法作一个分析 看看在规模n的所有可能输入中 那种输入会导致基本操作数C n 达到最大值 计算这个最差值Cworse n 后面讲到 通过确定算法运行时间的上界 分析最坏情况为算法效率提供一个非常重要的信息 也即 对于任何规模n的实例来讲 它保证算法运行时间不会超过最坏输入情况下的运行时间 Cworse n 最差效率分析的价值 顺序查找 Cworse n n2最优效率 当输入规模为n时 算法在最优情况下的效率 此时 相对于其他规模为n的输入 该算法运行时间最短 最快 顺序查找 Cbest n 1最优效率分析的价值 远不如最差效率分析重要 因不能指望每次输入都是最优输入 但它对算法的的选择有指导意义 例如 某算法在有序列表情况下效率很高 对于基本有序的输入数据 该算法可以获得接近最优输入的效率 实际中可考虑选择该算法 重要的是 如果一个算法的最优效率都不能满足实际需要 可立即抛弃该算法 12 平均效率 3平均效率无论是最优还是最差效率 都不能提供这样一种必要信息 在随机输入情况下 该算法具有怎样的行为 时间耗费 为此 引入平均效率 平均效率分析要比最差和最优效率分析困难很多 以后讨论平均效率时都引用其已知的推导结果 对推导有兴趣的同学 请查阅有关书籍 平均效率分析的价值 有许多重要算法的平均效率比它们过于悲观的最差效率要好很多 所以如果没有平均效率分析的话 我们会错失不少重要的算法 显然 我们不能通过求最优和最差效率平均值的方法来求平均效率 平均效率分析的直接法 1将输入分为几种类型 可能的话 目的是使得对于同种输入类型的实例 具有相同的基本操作数 2得到或者假设各类输入的概率分布 以推导出基本操作的平均次数 但各类输入的概率模型往往又难以验证 虽然它可能很合理 13 顺序查找算法的平均时间效率 顺序查找算法的平均时间效率 假设 1 成功查找的概率是p 0 p 1 查找不成功的概率是1 p 2 对任意第i次查找 第一次成功匹配 查找成功 发生在列表第i个位置的概率相同 即查找键位于列表任一位置上的概率相同1 n 基于假设 在列表任一位置上查找成功的概率为p 1 n 甚至可进一步假设p 0 5 若查找成功的位置为i 算法做的比较次数 基本操作 为i次 考虑成功查找概率 比较次数为p i n 若查找不成功 算法做的比较次数为n 列表全部查找一遍 考虑不成功查找概率 比较次数则为n 1 p 因此 算法平均效率 统计平均 14 摊销效率 4摊销效率它并不适合于算法的单次运行 而应用于算法对同样数据的多次运行 我们知道 在有些情况下单次运行的时间代价可能比较昂贵 但n次运行的总时间花费明显低于单次运行的最差效率乘以n 因此我们把最差效率的高成本摊到各次运行中去 即摊销效率 该做法与商业中把固定资产成本按其使用年限摊销到整个序列 各年 中的做法一致 通常 具备这种运行特性的算法是在一定程度上的具有 智能 的算法 通过 学习 获得 知识 累积 再运用知识库中的有关知识对算法下次如何执行提供指导 从而提高以后运行的效率 一个例子 汉字拼音输入法中的动态词频调整算法 它统计不同用户对某些字词的使用率 学习积累过程 来动态调整这些字词下次出现的先后顺序 高频先现 达到减少用户翻阅时间的目的 提高了该算法的执行效率 后续章节中 除非专门说明 都将最差情况下时间耗费的极限作为算法的时间耗费 称时间复杂性或时间效率 求解过程称为时间渐进分析 15 渐进符号 渐进符号和基本效率类型上节指出 效率分析主要关心的是一个算法的基本操作数随问题规模的增长率 增长次数 即问题规模n变大情况下 该算法的基本操作数增长的快慢 它是规模n的函数 增长函数 为了对增长函数作出比较和归类 通常使用三种符号 O theta 下面就这些符号先作一个非正式介绍 便于理解 T n 和g n 定义在自然数集合上的任意非负函数 n取自然数 T n 算法的运行时间函数 常用基本操作数增长函数C n 表示 g n 与增长函数作比较的函数 非正式介绍O g n 增长次数小于等于g n 包括其常数倍 n趋于无穷大 的函数集合 即g n 是增长函数集的上界 例如 16 上界符号 g n 增长次数大于等于g n 包括其常数倍 n趋于无穷大 的函数集合 即g n 是增长函数集的下界 例如 g n 增长次数等于g n 包括其常数倍 n趋于无穷大 的函数集合 即g n 与增长函数集同阶 相同的增长率 例如 上界符号O 最常用 定义 把函数T n 包含在O g n 中 记为T n O g n 它成立的条件是 对于足够大的n T n 的上界由g n 的常数倍决定 即存在正数c和非负整数n0 使得下式成立 17 下界符号 证明 证一 据定义选取 证二 据定义选取 下届符号 定义 把函数T n 包含在 g n 中 记为T n g n 它成立的条件是 对于足够大的n T n 的下界由g n 的常数倍决定 即存在正数c和非负整数n0 使得下式成立 规模 增长函数 n0之前情况无关紧要 下界 最佳效率分析 18 同阶符号 同阶符号 定义 把函数T n 包含在 g n 中 记为T n g n 它成立的条件是 对于足够大的n T n 的下界和上界均由g n 的常数倍决定 即存在正数c和非负整数n0 使得 例 证明证 注意到上界情况 下界情况 19 渐进符号的有用性质 渐进符号的有用性质 1 2 3证明从略 性质1 性质2 性质3 性质4 性质4的价值 证明见下页 某些算法是由两个 以上 执行部分组成 性质4指明 该算法的整体效率由具有较大增长率的部分决定 即它效率最差的部分 举例如下 数组中特定元素的查找算法 第一部分 用某种已知的排序算法对数组排序 得到有序数组 第二部分 对有序数组从头至尾扫描 比较是否与指定元素相等 若排序部分增长函数为0 5n n 1 O n2 第二部分的增长函数为n O n 那么 算法的整体效率为T n O n2 20 渐进符号性质4的证明 性质4的证明 21 利用极限比较增长率 利用极限比较增长率 此法常用来比较两个特定增长函数的增长率 简便 它根据极限定义 对两个函数的比值求极限 以判定哪个函数增长更快 例1 比较0 5n n 1 和n2的增长率 或证明 0 5n n 1 n2 22 利用极限比较增长率例 例2 例3 23 渐进效率的基本类型 渐进效率的基本类型 24 非递归算法分析 非递归算法的效率分析 很常用 本节将系统地运用前节的通用框架来分析非递归算法的效率 先从一个简单的算法开始 示范这类算法分析的步骤 例1 从n个元素列表中查找最大值 用数组简单实现列表 算法MaxElement A 0 n 1 求数组A中元素的最大值 输入 实数数组A 输出 A中最大元素的值maxval A 0 fori 1ton 1doifA i maxval 每次循环时无条件执行 必执行 maxval A i 每次循环时有条件执行 不一定执行 returnmaxval效率分析框架要求明确输入规模和基本操作 输入规模 数组元素的个数n 基本操作 根据基本操作概念 它应该是算法中最费时的操作 因此 应该选择for循环内的比较操作 本算法每个数组元素都要进行一次比较 故不区分最优 最差和平均效率 25 非递归算法分析2 接下来 效率分析框架要求我们找到基本操作与输入规模的函数关系 即增长函数T n 或者C n 这里 C n 是比较运算的次数 不难看出 本算法每循环一次 基本操作就要执行一次 因此有 非递归算法效率分析的通用方案 1确定输入规模 2确定基本操作 一般情况 它总是位于算法的最内层循环里 3考虑基本操作的执行次数是否仅仅与输入规模有关 若还与其他因数有关 比如顺序查找算法中基本操作执行次数还与查找键在列表中的位置有关 则按需要对最差 最佳 平均效率作出分析 4建立基本操作执行次数与输入规模n的求和表达式 即增长函数 5利用运算公式 法则 确定该增长函数的增长率 结论 本算法具有线性增长率 26 复习 几个常用求和公式 复习 几个常用求和公式 27 例2 元素唯一性问题 例2 元素唯一性问题 检查给定数组的元素是否全部唯一算法 UniqueElement A 0 n 1 fori 0ton 2doforj i 1ton 1doifA i A j returnfalsereturntrue输入规模 数组元素个数n基本操作 最内层循环只有一个 比较 操作 选为基本操作 效率种类 从循环结束条件可知 若比较的两个元素相等 则提前结束循环 返回 假 说明数组元素不唯一 最佳的情况是 首次比较就结束循环 即数组开始两个元素就相同 最差的情况是 循环结束前的最后一次比较才发现相同的元素 最后两个 或者该数组没有相同元素 都要完成全部循环次数 即比较次数就是循环次数 这里 我们研究其最差效率Cworst n i j 28 例2 元素唯一性问题 续 外层i循环范围 0 n 2 内层j循环范围 i 1 n 1建立增长函数 基本操作执行次数与输入规模n的求和表达式 29 例3 矩阵乘法 时间效率分析 例3 矩阵乘法 时间效率分析给定两个方阵A和B 根据矩阵乘法定义计算它们之乘积 算法 MatrixMultiplication A 0 n 1 0 n 1 B 0 n 1 0 n 1 fori 0ton 1do 行循环forj 0ton 1do 列循环M i j 0 0 初始化fork 0ton 1do 用变量k表示变化的脚标M i j M i j A i k B k j returnM 列 行 如果是非方阵 只需改变行列循环变量的范围即可 本例均为n 1 30 例3 矩阵乘法 时间效率分析 续 输入规模 因是方阵 选择矩阵的阶n 否则 选参与运算的元素数 基本操作 最内层循环有三种操作 乘法 加法 赋值 每次循环时 每种操作均被执行一次 所以任选一种作为基本操作均可 因为它们的执行次数都一样 但考虑操作的时间耗费 对大多数计算机来讲 乘法比加法更费时间 且算术运算比赋值操作更费时间 所以 本例选乘法作为基本操作 效率种类 因为本算例的基本操作数只与输入规模有关 所以不必分别研究最佳 最差和平均效率 就是一种时间效率 建立增长函数 基本操作数与输入规模n的求和表达式 31 例4 二进制位数 一个十进制正整数的二进制位数 例4 二进制位数 一个十进制正整数n的二进制位数b 算法 Binary n count 1whilen 1docount count 1n returncount输入规模 该正整数的大小n 基本操作 选循环内的除法操作 效率种类 因基本操作执行次数只与规模n有关 无需分别研究最佳 最差和平均效率 增长函数 本例基本操作增长函数不是一个求和表达式 需要用其他的方法来计算循环次数 基本操作执行次数 可建立递推式来求解 后面两节介绍 另外方法 本例循环次数为 32 递归算法效率分析 递归算法效率分析序列和递推关系定义 数字序列是数字的一个有序列表 例如 2 4 6 8 10 12 正偶数序列 0 1 1 2 3 5 8 裴波拉契数序列 序列的函数表示法 x n 把序列表示为一个函数 自变量n 表示一个元素在序列中的位置即序号 函数值x n 表示该元素本身 如正偶数序列第2个元素 x n 称为该序列的通项 序列的两种定义法 1 通项定义法 例如正偶数序列2 方程定义法 把序列的通项和其他项用方程定义 并规定序列的首项或前几项的值 例如 递推方程或递推关系 简称递推式 初始条件 33 解递推方程的概念 解递推方程的概念解递推方程 意味着找到序列通项 既满足递推式又满足初始条件 或证明这样一个序列不存在 递推方程无解 如下递推式的解 验证递推方程 代入法验证 验证初始条件 递推方程的通解 通常 有无穷多个序列 解 满足同一个递推方程 因此 通解一般包括若干任意常数 本例递推方程的特解 满足递推方程的一个特定的序列 解 通常是那个满足初始条件的特解 一个特定序列由初始条件 初值 确定 不包括初始条件 34 递推方程求解 前向替换法 递推方程的求解方法不存在对每一个递推方程都有效的一种通用方法 这就象对简单的一元方程f x 0不能得到它的通解一样 前向替换法 递推方向 前 后从序列首项 由初始条件给出 开始 使用递推式生成序列的前几项 希望通过对前几项的观察找到序列的通项 并进行验证 例子如下 递推式 根据初始条件和递推式 生成序列前几项 通项 方法评价 有时候很难从序列前几项中找到通项 汉诺 hanoi 塔游戏 35 递推方程求解 反向替换法 反向替换法 很有效 递推方向 前 后用递推式将x n 逐次表示为x n 1 x n 2 x n 3 x n k k 1 2 3 然后通过运算化简 得序列通项 解 例子 递推式 根据初始条件 n 0 要求 n k 0 上式变为 该法所得通项是直接由递推式推出来的 故无需验证 36 递推方程求解 二阶常系数线性递推式 公式法 解二阶常系数线性递推方程问题提出 有一类重要递推式不能用前向和反向替换法求解 形如 概念解释 1 二阶 递推式中未知项x n 和x n 2 在序列中相差两个位置 2 常系数 递推式中未知项系数为常数 3 线性 递推式为未知项的线性组合 4 齐次 方程右端为0 即f n 0 5 非齐次 方程右端不为0 6 特征方程 齐次递推方程的解 取决于和递推式具有相同系数的一个二次方程即特征方程 定理1 设q1 q2是特征方程的两个根 第一种情况 有两个不相等实根 齐次递推方程通解为 c1和c2为待定常数 37 递推方程求解 二阶常系数线性递推式例1 第二种情况 有两个相等实根 齐次递推方程通解为 第三种情况 特征方程在实数域无解 略 定理2 把非齐次方程的特解和相应的齐次方程通解相加 得到该非齐次方程的通解 例1 求齐次递推方程通解和特解解 该递推方程的特征方程为 特征方程有两个相等的实根 根据定理1 该递推方程通解为 根据初始条件解出待定常数 得到一个特解 c1和c2为待定常数 c1和c2为待定常数 38 递推方程求解 二阶常系数线性递推式例2 例2 求非齐次递推方程满足初始条件的特解解 根据例1 该非齐次方程对应的齐次方程的通解为 注意 此时不能代入初始条件解出非齐次方程的一个特解 为什么 现在 求非齐次方程的一个特解 设特解为 由递推式解得根据定理2 得到非齐次递推方程的通解 叠加 据初始条件解出特解中待定常数 得特解 c1和c2为待定常数 c1和c2为待定常数 39 递推方程求解 k阶常系数线性递推式 公式法求解 k阶常系数线性递推式 二阶的推广 它的齐次递推方程 方程右端项为0 即齐次方程的特征方程 相同系数的一个k次方程 超越方程 数值解法 40 递推方程求解 k阶常系数线性递推式 2 求k阶齐次递推方程通解 定理1推广 1 特征方程有k个不相等实根qk 齐次递推方程通解为 2 特征方程有r个相等实根 重根 齐次递推方程通解为 说明 k次特征方程有k个实根q1 q2 qk 其中有r个实根相同 这相同的r个实根为 ck为待定常数 41 递推方程求解 k阶常系数线性递推式 3 求k阶非齐次递推方程特解 前面已求得其相应的齐次递推方程通解 据定理2 再求得非齐次方程的任意一个特解 则两者相加可得非齐次递推方程通解 最后 根据给定初始条件可得满足初始条件的非齐次递推方程特解 对一般的非齐次递推方程 不存在寻找特解的通用方法 只能用观察法去假定特解的形式 然后用待定系数法确定系数 1 当f n 是n的t次多项式时 可设特解也是n的多项式即特解形式 2 当f n 是n的指数函数 a b为待定常数时 设特解形式 1 b不是相应齐次方程的特征根时 2 b是相应齐次方程的e重特征根时 p为待定系数 42 递推方程求解 k阶常系数线性递推式例 例 解递归方程解 1 求齐次递推方程的特征根