算法设计与分析第2章.ppt

第2章算法分析基础 2020 3 31 成都学院计算机系 2 2 1算法复杂度2 2渐近表示法2 3递推关系 2020 3 31 成都学院计算机系 3 主要知识点 掌握好算法的评价标准 了解影响程序运行时间的因素 掌握算法的评价标准 时间复杂度和空间复杂度的概念 掌握渐近时间复杂度的几种表示方式 掌握常见时间复杂度渐近表示之间的关系 2 1算法复杂度 2020 3 31 成都学院计算机系 5 2 1 1什么是好的算法 好的算法一个好的算法应具有以下4个重要特性 正确性 correctness 算法的执行结果应当满足预先规定的功能和性能要求 简明性 simplicity 算法应思路清晰 层次分明 容易理解 利于编码和调试 效率 efficiency 算法应有效使用存储空间 并具有高的时间效率 最优性 optimality 算法的执行时间已达到求解该类问题所需时间的下界 2020 3 31 成都学院计算机系 6 程序健壮性是指当输入不合法数据时 程序应能做适当处理而不至于引起严重后果 其含义是 当程序万一遇到意外时 能按某种预定方式做出适当处理 正确性和健壮性是相互补充的 2020 3 31 成都学院计算机系 7 2 1 2影响程序运行时间的因素 程序运行时间是指程序从开始到结束所需的时间 程序运行所需的时间依赖于计算机软 硬件系统 在完全相同的计算机环境下 影响程序运行时间的因素主要有 程序所依赖的算法 问题规模和输入数据 计算机系统性能 2020 3 31 成都学院计算机系 8 算法效率的度量分为事前估计和后期测试 后期测试主要通过在算法中的某些部位插装时间函数来测定算法完成某一功能所需的时间 事前估计主要是分析算法的复杂性 包括空间复杂度和时间复杂度 算法的时间复杂性T n 算法的空间复杂性S n 其中n是问题的规模 输入大小 2020 3 31 成都学院计算机系 9 1 事前分析目的 试图得出关于算法执行特性的一种形式描述 以 理论上 衡量算法的 好坏 如何给出反映算法执行特性的描述 最直接方法 统计算法中各种运算的执行情况 包括 运用了哪些运算每种运算被执行的次数该种运算执行一次所花费的时间等 算法的执行时间 Fi ti 2020 3 31 成都学院计算机系 10 频率计数例 x x yfori 1tondofori 1tondox x yforj 1tondorepeatx x yrepeatrepeat a b c 分析 a x x y执行了1次 b x x y执行了n次 c x x y执行了n2次定义 频率计数 一条语句或一种运算在算法 或程序 体中的执行次数 2020 3 31 成都学院计算机系 11 一条语句在整个程序运行时实际执行时间 频率计数 每执行一次该语句所需的时间如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素 如机器类型 编程与语言 操作系统等 没有统一的描述模型 在事前分析中 只限于确定与所使用的机器及其他环境因素无关的频率计数 依此建立理论分析模型 2020 3 31 成都学院计算机系 12 数量级语句的数量级 语句的执行频率例 1 n n2算法的数量级 算法所包含的所有语句的执行频率之和 算法的数量级从本质上反映了一个算法的执行特性 例 假如求解同一个问题的三个算法分别具有n n2 n3数量级 若n 10 则可能的执行时间将分别是10 100 1000个单位时间 与环境因素无关 2020 3 31 成都学院计算机系 13 计算时间 频率计数的表示函数通过事前分析给出算法计算时间 频率计数 的一个函数表示形式 一般记为与输入规模n有关的函数形式 f n 注 最高次项与函数整体的关系空间特性分析 略 2020 3 31 成都学院计算机系 14 2 事后测试目的 运行程序 确定程序实际耗费的时间与空间 验证先前的分析结论 包括正确性 执行性能等 比较 优化所设计的算法 分析手段 作时 空性能分布图 2020 3 31 成都学院计算机系 15 2 1 3算法的时间复杂度 抽象机模型设抽象机提供由m个基本运算 也可称为语句 组成的运算集O O1 O2 Om 每个运算都是基本的 它们的执行时间是有限常量 同时设执行第i个运算Oi所需的时间是 i 1 i m 一个算法对于给定的抽象机上的一次执行过程 表现为执行一个基本运算的序列 2020 3 31 成都学院计算机系 16 时间复杂度一个算法的时间复杂度 timecomplexity 是指算法运行所需的时间 设有一个在抽象机上运行的算法A I是某次运行时的输入数据 其规模为n 则算法A的运行时间T是n和I的函数 记做T n I 又设在该次运算中抽象机的第i个基本运算Oi的执行次数为 i 1 i m i也是n和I的函数 记做 i n I 那么 算法A在输入为I时的运行时间是 2020 3 31 成都学院计算机系 17 称为算法的时间复杂度 其中 输入数据I是问题的实例 n是问题的规模 要全面分析一个算法 需要考虑算法在最坏情况下的时间代价 在最好情况下的时间代价以及在平均情况下的时间代价 2020 3 31 成都学院计算机系 18 最好 最坏和平均时间复杂度最好时间复杂度B n 最坏时间复杂度W n 平均时间复杂度A n Dn是规模为n的所有合法输入的集合 I 和I 分别为Dn中算法运行最好和最坏情况的输入数据 P I 是输入数据I在具体应用中被使用的概率 2020 3 31 成都学院计算机系 19 2 1 4使用程序步分析算法 一个程序步 programstep 是指在语法上或语义上有意义的程序段 该程序段的执行时间必须与问题实例的规模无关 2020 3 31 成都学院计算机系 20 程序2 1 求数组元素累加之和的迭代程序floatSum floatlist constintn floattempsum 0 0 count 针对赋值语句for inti 0 i n i count 针对for循环语句tempsum list i count 针对赋值语句 count 针对for的最后一次执行count 针对return语句returntempsum 2020 3 31 成都学院计算机系 21 程序2 2 求数组元素累加之和的递归程序floatRSum floatlist constintn count 针对if条件if n count 针对RSum调用和return语句returnRSum list n 1 list n 1 count 针对return语句return0 2020 3 31 成都学院计算机系 22 设RSum list n 的程序步为T n T n 2 T n 1 2 2 T n 2 2 3 T n 3 2 n T 0 2 n 2 2020 3 31 成都学院计算机系 23 2 1 5算法的空间复杂度 空间复杂度 spacecomplexity 是指算法运行所需的存储空间 程序运行所需的存储空间包括以下两部分 固定空间需求 fixedspacerequirement 这部分空间与所处理数据的大小和个数无关 也就是说 与问题实例的特征无关 可变空间需求 variablespacerequirement 这部分空间大小与算法在某次执行中处理的特定数据的规模有关 2 2渐近表示法 2020 3 31 成都学院计算机系 25 算法渐近复杂性概念 T n 当n 时有 T n t n T n 0t n 是T n 的渐近性态 为算法的渐近复杂性 在数学上 t n 是T n 的渐近表达式 实质是T n 略去低阶项留下的主项 它比T n 简单 2020 3 31 成都学院计算机系 26 例T n 3N2 4NlogN 7时 求它的一个渐近表达式t n 的一个答案是3N2 2020 3 31 成都学院计算机系 27 记 算法的计算时间为f n 数量级限界函数为g n 其中 n是输入或输出规模的某种测度 f n 表示算法的 实际 执行时间 与机器及语言有关 g n 是形式简单的函数 如nm logn 2n n 等 是事前分析中通过对计算时间或频率计数统计分析所得的 与机器及语言无关的函数 以下给出算法执行时间 上界 下界 平均 的定义 2020 3 31 成都学院计算机系 28 2 2 1渐近上界记号 O 如果存在两个正常数c和n0 对于所有的n n0 有 f n c g n 则记作f n g n 称为大O记号 bigOhnotation 使用大O记号及后面定义的几种渐近表示法表示的算法时间复杂度 称为算法的渐近时间复杂度 asymptoticcomplexity 2020 3 31 成都学院计算机系 29 例1f n 2n 3是否等于O n 当n 3时 2n 3 3n可选c 3 n0 3 对于n n0 f n 2n 3 3n 所以 f n O n 即2n 3 O n 2020 3 31 成都学院计算机系 30 例2f n 10n2 4n 2的O表示形式 对于n 2时 10n2 4n 2 10n2 5n并且当n 5时 5n n2因此 可选c 11 n0 5 对于n n0 f n 10n2 4n 2 11n2所以f n O n2 2020 3 31 成都学院计算机系 31 例3证明 f n n O nn 证 n n n 1 n 2 1对于n 1时 n n 1 n 2 1 nn因此 可选c 1 n0 1对于n n0 f n n nn所以 f n O nn 2020 3 31 成都学院计算机系 32 例410n2 9 O n 使用反证法假定存在c和n0 使得对于n n0 10n2 9 cn始终成立 那么有10n 9 n c 即n c 10 9 10n 总成立 但此不等式不可能总成立 取n c 10 1时 该不等式便不再成立 2020 3 31 成都学院计算机系 33 定理2 1如果f n amnm am 1nm 1 a1n a0是m次多项式 且am 0 则f n O nm 证明 取n0 1 当n n0时 有f n amnm am 1nm 1 a1n a0 am nm am 1 nm 1 a1 n a0 am am 1 n a1 nm 1 a0 nm nm am am 1 a1 a0 nm取c am am 1 a1 a0 定理得证 2020 3 31 成都学院计算机系 34 只要适当选择关键操作 算法的渐近时间复杂度可以由关键操作的执行次数之和来计算 一般地 关键操作的执行次数与问题的规模有关 是n的函数 2020 3 31 成都学院计算机系 35 程序2 3 矩阵乘法for i 0 i n i n 1for j 0 j n j n n 1 c i j 0 n2for k 0 k n k n2 n 1 c i j a i k b k j n3 2020 3 31 成都学院计算机系 36 2 2 2渐近下界记号 如果存在两个正常数c和n0 对于所有的n n0 有 f n c g n 则记作f n g n 称为 记号 omeganotation 2020 3 31 成都学院计算机系 37 例5f n 2n 3 n 对所有n 2n 3 2n可选c 2 n0 0 对于n n0 f n 2n 3 2n所以 f n n 即2n 3 n 2020 3 31 成都学院计算机系 38 例6f n 10n2 4n 2 n2 对所有n 10n2 4n 2 10n2可选c 10 n0 0对于n n0 f n 10n2 4n 2 10n2所以 f n n2 2020 3 31 成都学院计算机系 39 定理2 2如果f n amnm am 1nm 1 a1n a0是m次多项式 且am 0 则f n nm 课后自己证明 2020 3 31 成都学院计算机系 40 2 2 3 记号 如果存在正常数c1 c2和n0 对于所有的n n0 有c1 g n f n c2 g n 则记作f n g n 称为 记号 Thetanotation g n 表示所有增长阶数与g n 相同的函数的集合 用于表示一个算法运行时间具有与g n 相同的阶 2020 3 31 成都学院计算机系 41 例7f n 2n 3 n 即2n 3 n 例8f n 10n2 4n 2 n2 定理2 3如果f n amnm am 1nm 1 a1n a0是m次多项式 且am 0 则f n nm 2020 3 31 成都学院计算机系 42 2 2 4小o记号 f n o g n 当且仅当f n O g n 且f n g n o g n 表示所有增长阶数小于g n 的所有函数的集合 用于表示一个算法运行时间f n 的阶比g n 低 例f n 2n 3 o n2 即2n 3 o n2 2020 3 31 成都学院计算机系 43 2 2 5渐近分析记号的性质 1 传递性 f n O g n g n O h n f n O h n f n g n g n h n f n h n f n g n g n h n f n h n f n o g n g n o h n f n o h n 2020 3 31 成都学院计算机系 44 2 反身性 f n f n f n O f n f n f n 3 对称性 f n g n g n f n 4 互对称性 f n O g n g n f n 2020 3 31 成都学院计算机系 45 5 算术运算 O f n O g n O max f n g n O f n O g n O f n g n O f n O g n O f n g n O cf n O f n g n O f n O f n O g n O f n 2020 3 31 成都学院计算机系 46 算法渐近复杂性分析中常用函数 1 单调函数单调递增 m n f m f n 单调递减 m n f m f n 严格单调递增 mf n 2 取整函数 x 不大于x的最大整数 x 不小于x的最小整数 2020 3 31 成都学院计算机系 47 取整函数的若干性质 x 10 有 n a b n ab n a b n ab a b a b 1 b a b a b 1 b f x x g x x 为单调递增函数 2020 3 31 成都学院计算机系 48 3 多项式函数p n a0 a1n a2n2 adnd ad 0 p n nd f n O nk f n 多项式有界 f n O 1 f n c 2020 3 31 成都学院计算机系 49 4 指数函数对于正整数m n和实数a 0 a0 1 a1 a a 1 1 a am n amn am n an m aman am n a 1 an为单调递增函数 a 1 nb o an 2020 3 31 成都学院计算机系 50 ex 1 x x 1 1 x ex 1 x x2 ex 1 x x2 asx 0 2020 3 31 成都学院计算机系 51 5 对数函数logn log2n lgn log10n lnn logen logkn logn k loglogn log logn fora 0 b 0 c 0 2020 3 31 成都学院计算机系 52 2020 3 31 成都学院计算机系 53 x 1 forx 1 foranya 0 logbn o na 2020 3 31 成都学院计算机系 54 2 2 5算法按时间复杂度分类 算法按计算时间分类凡渐近时间复杂度有多项式时间限界的算法称做多项式时间算法 polynomialtimealgorithm 而渐近时间复杂度为指数函数限界的算法称做指数时间算法 exponentialtimealgorithm 2020 3 31 成都学院计算机系 55 最常见的多项式时间算法的渐近时间复杂度O 1 O logn O n O nlogn O n2 O n3 最常见的指数时间算法的渐近时间复杂度O 2n O n O nn 2020 3 31 成都学院计算机系 56 2020 3 31 成都学院计算机系 57 2 3递推关系 2020 3 31 成都学院计算机系 59 2 3 1递推方程 递推方程 recurrenceequation 是自然数上一个函数T n 它使用