第2章 复杂度分析

《第2章 复杂度分析》由会员分享，可在线阅读，更多相关《第2章 复杂度分析（19页珍藏版）》请在金锄头文库上搜索。

1、第2章 复杂度分析 2 1 计算复杂度和渐进复杂度计算复杂度和渐进复杂度 同一个问题往往可以由不同的算法解决 但是算法不同 效率也不同 对于处理数量较少 的数据项而言 算法之间效率的差异也许微不足道 但是当数据量增长时 这种差异就会成比 例地增长 为了使得算法效率具有可比性 Juris Hartmanis 和 Richard E Stearns 引入一种称为 计 算复杂度 的度量标准来衡量一种算法的难易程度 计算复杂度表示应用一种算法需要付出多大的努力或是成本是多少 这种成本可以用很多 标准衡量 特定的应用场合决定了成本的不同含义 本书介绍两种衡量效率的标准 时间标准 和空间标准 由于时间因素

2、较之空间因素更为重要 所以考虑效率时通常关注处理数据所花费 的时间 然而 即使是效率最低的算法 当运行在 Cray 计算机上时 也会比效率最高的算法在 PC 机上运行的执行效率要高 所以运行时间通常是系统相关的 举个例子 为了对一百个算法 进行比较 就必须在同一台机器上运行这些算法 并且 即使在同一台机器上运行 运行时间 的测试结果还跟算法所采用的语言有关 编译程序执行起来比解释程序要快得多 同一个程序 用 C 或 Pascal 写就比用 BASIC 或 LISP 写要快约 20 倍 要评估一种算法的效率 就不能使用微秒或纳秒这样的实际时间单位 而应该采用某种逻 辑单位 描述一个文件或数组的尺

3、寸 n 同处理这些数据所需的时间 t 之间的关系 如果尺寸 n 和时间 t 之间是线性关系 即 那么数据量增长 5 倍将会使处理时间增长同样的倍数 11 cnt 即如果 就有 同样 如果 那么 n 翻倍只会让 t 增长一个时间单位 12 5nn 12 5tt nt 21 log 即 若 那么 2 log2 2 nt 1 12 tt 通常来说 表示 n 与 t 之间关系的函数式会比上面的函数式要复杂得多 只有当涉及的数 据量巨大时 计算这样的函数式才显得重要 任何不会从实质上改变函数式数量级的项都应当 从函数式中剔除 经过处理后的函数式给出的是原有函数式的近似效率估量 但这种近似的效 率估量与原

4、函数相比 在效率上足够接近 当函数式处理的数据量很大时尤其如此 这种效率 的估量就称为渐进复杂度 在两种情况下常采用这种复杂度 第一种情况是 在忽略函数式特 定项来表达一个算法效率时 另一种情况是 在函数式的精确表示非常困难 或不可能得到这 种精确表示 而只能进行近似表示时 为了说明第一种情况 考虑以下例子 2 1 1000log100 10 2 nnnnf 如果 n 较小 最后一项 1000 是最大的 当 n 等于 10 时 第二项 100n 和最后一项 1000 相同 而其余项所占函数式总值的比重小 当 n 达到 100 时 第一项和第二项在结果中所占的比重是 第 2 章 复杂度分析 49

5、 一样的 但当 n 超过 100 时 第二项所占的比重开始减小 所以 对于大值的 n 来说 因第一 项 是以平方速度增长 故函数 f 的值主要由第一项决定 如表 2 1 所示 其余项都可以忽 2 n 略不计 表 2 1 函数中所有项的增长速度 1000log100 10 2 nnnnf n f n n2 及影响比重 100n 及影响比重 log10n 及影响 比重 1000 及影响 比重 1 1101 1 0 1 100 9 1 0 0 0 1000 90 82 10 2101 100 4 76 1000 47 6 1 0 05 1000 47 62 100 21002 10000 47 6

6、10000 47 6 2 0 991 1000 4 76 1000 1101003 1000000 90 8 100000 9 1 3 0 0003 1000 0 09 10000 101001004 1000000000 99 0 1000000 0 99 4 0 0 1000 0 001 100000 10010001005 10000000000 99 9 10000000 0 099 5 0 0 1000 0 00 2 2 大大 O 符号符号 最常用来描述渐进复杂度 即用来估计函数增长率的 是由 Paul Bachmann 于 1894 年引入 的大 O 符号 给定两正值函数 f 和

7、g 考虑以下定义 定义 1 条件为 存在正数 c 和 N 使得对于所有的 有 ngOnf Nn ncgnf 上述定义表明 如果对于足够大的 n 或者说大于某自然数 N 的 n 存在正数 c 使得 f 不 大于 cg 则 f 是 g 的大 O 表示 f 和 g 的关系既可以理解为 g n 是 f n 的一个上界 也可以理解 为 f 最终至多增长得跟 g 一样快 这种定义的问题在于 首先 它只声明一定存在某个 c 和 N 但没有给出怎么求出这两个 常数的任何提示 其次 它并未给这些值以任何限制 当有许多可能的值时 并不知道如何选 择 实际上 对于同一对 f 和 g 通常可以指定无数对 c 和 N

8、例如 2 2 132 22 nOnnnf 在这里 c 和 N 的计算结果如表 2 2 所示 2 nng 表 2 2 对于函数 根据大 O 定义计算得到的 c 和 N 的不同值 132 22 nOnnnf c 6 4 3 3 9 1 3 16 13 2 25 16 2 2 N 1 2 3 4 5 对于不同的 n 我们通过计算下面的不等式得到表 2 2 中的这些值 数据结构与算法 50 22 132cnnn 或等价不等式 c nn 2 13 2 通过将大 O 符号定义中的 f n 以等式 2 2 的二次函数代入 即将 g n 以代入 就可以得到第 2 n 一个不等式 由于在一个不等式中有两个未知数

9、 对于同一函数 g 即 就会存在不同的常数 2 n 对 c 和 N 为了选择最好的 c 和 N 我们将标准定为对于选择的 N f 中的某项应该是最大且始 终是最大项 在等式 2 2 中 惟一可能的最大项就是和 3n 可使用不等式来进行 2 2nnn32 2 比较 使得对于不等式总是成立 因而得出 N 2 及 如表 2 2 所示 1 n 4 3 3c 那么 刚才所列出的常数对有什么实际意义呢 它们都跟同一函数式和 f n 有关 2 nng 对于一个固定的 g 可以得出有限的常数对 c 和 N 关键在于 f 和 g 以相同速率增长 而定义表 明 当 g 乘以一个常数 c 后几乎总是大于或等于 f

10、几乎总是 是对于所有不小于常数 N 的 n 而言的 该事实说明 c 的值决定于所选取的 N 反之亦然 比如说 如果 N 取 1 的话 即 如果要 g 乘以 c 使得 cg n 马上不小于 f 那么 c 必须等于 6 或更大的值 如果 cg n 是从 n 2 开始大于等于 f n 那么 c 只要等于 3 75 就足够了 如果 cg n 从 n 3 开始不小于 f n 则常数 c 至少要等于 图 2 1 给出了函数 f 和 g 的图示 函数 g 使用不同的 c 作为系数绘制 而 N 总 9 1 3 是位于函数 cg n 和 f 的交点位置 图 2 1 函数 f 和 g 图示 而大 O 符号固有的不

11、精确性还会导致其他的问题 因为对于一个给定函数 f 有无限多的 g 函数 对于等式 2 2 的 f 它不仅是的大 O 它还是 其中 的大 2 n 3 n 4 n k n2 k O 为了避免这种情况 我们取最小的 g 函数 在这里就是 2 n 函数 f 的近似表示可以采用大 O 符号进行求精 只取压缩了不重要的信息的部分 比如 在等式 2 1 中 第三项和最后一项在函数中所占的比重可以忽略不计 2 3 log100 10 2 nOnnnf 类似地 等式中 2 2 中的函数 f 可以近似为 第 2 章 复杂度分析 51 2 4 2 2 nOnnf 2 3 大大 O 符号的性质符号的性质 在估计算法

12、效率时 我们可以利用大 O 符号的许多有用的性质 性质 1 传递性 如果 那么 也可认为等 ngOnf nhOng nhOnf ngOO 于 ngO 证明 根据定义 若 则存在 c1和 N1 使得对于所有 有 同 ngOnf 1 Nn 1 ngcnf 样 则存在正数 c2和 N2使得所有 有 nhOng 2 Nn 2 nhcng 因此 对于所有有 其中 N 为 N1与 N2中较大者 只要取 则Nn 211 nhccngc 21c cc 对于所有的有 即 f 是 h n 的大 O Nn nchnf 性质 2 如果且 则 nhOnf nhOng nhOngnf 证明 只要令 就有 21 ccc n

13、chngnf 性质 3 kk nOan 证明 只要令 不等式恒成立 ac kk cnan 性质 4 对于任何正数 j jkk nOn 证明 只要令 c N 1 从以上性质可以推出 任何多项式都是该多项式中次数最大的项的大 O 即 01 1 1 kk k k k nOananananf 很显然 在以上多项式中 对于任何正数 j jk nOnf 数据结构与算法 52 在算法效率估计中 一个非常重要的函数就是对数函数 其实可以说 如果某一个算法的 复杂度为一个对数函数 则可以说该算法已经很不错了 虽然有很多函数看起来比对数函数好 但其中仅有少数几个 如或 有实际意义 在学习对数函数的一个重要性质前

14、我 lg lgnO 1 O 们先不证明以下性质 性质 5 如果 则 ncgnf ngOnf 性质 6 对于任意正数 a b b 1 有 loglognOn ba 该性质表明对数函数间存在着对应关系 性质 6 表明 无论底数为何 对数函数互为大 O 即 所有这些函数都有同样的增长速度 证明 令 根据对数定义 有 xn a logyn b lognbna yx 对两边同时取 ln 得 nby nax lnln lnln 故 ncn a b n nbna byax bba ba loglog ln ln log loglnlogln lnln 这证明和互为倍数 根据性质 5 n a logn b l

15、og loglognOn ba 由于在大 O 符号中对数的底数没有影响 我们可以只用一种底数 性质 6 就可以写成 性质 7 对于任何正数 a 1 其中 lglognOn a nn 2 loglg 2 4 符号与符号与 符号符号 大 O 符号表示函数的上界 对应于大 O 符号的定义 也有一个下界的定义 定义 2 条 件 为 存 在 正 的 常 数 c 和 N 使 得 对 于 所 有 的 有 ngnf Nn ncgnf 上述定义表明 f 是 g 的大 表示 如果有一正数 c 对于几乎所有的 n 使得 f 不小于 cg 第 2 章 复杂度分析 53 换句话说 cg n 是 f n 大小的下界 最终

16、 f 至少以速率 g 增长 该定义与大 O 符号定义的惟一不同之处就在于不等式的方向 将 换成 就把 一个定义变成另一个定义 可以用一个等式来表示两符号之间的联系 nfniffgngnf 符号跟大 O 符号同样都有冗余问题 c 和 N 有无限多种选择 对于等式 2 2 我们就是 要找到一个 c 使得 如果 那么对于任意的该不等式都成立 其 22 132cnnn 2 c0 n 中 2 是图 2 2 中 c 的界限 还有 如果 且 那么 这就是说 只要我 gf gh hf 们能找到这样一个 g 而使 那么我们就能找到无限多个 比方说 函数 2 2 是 gf 2 n 的 但也是 n n1 4 n1 3 n1 2 还有 以及其他许多函数的 出于实际需要 nlgnlglg 我们只对最接近的 即最大的下界 感兴趣 每次我们选择函数 f的 时都有只考虑最接近的 对于函数 f 有无限个可能的下界 也就是说 跟 f 有无限个上界一样 f 也有一个无限大 的 g 的集合 使得 为了避免混乱 我们将只关心最小的上界和最大的下界 注 ngnf 意到两个符号的定义中的那个等号 它指出了大 O 和 符号的公共部分