算法分析与问题的计算复杂度

算法分析与问题的计算复杂度 王子辰 2016.5.20

概要 第一部分检索 算法的评价指标 平凡下界 决策树与时间复杂度 第二部分排序 冒泡排序 堆排序等排序算法 排序算法的复杂度下界 第三部分选择 选择问题的时间复杂度分析 问题之间的归约性

概要 第一部分检索 算法的评价指标 平凡下界 决策树与时间复杂度 第二部分排序 冒泡排序 堆排序等排序算法 排序算法的复杂度下界 第三部分选择 选择问题的时间复杂度分析 问题之间的归约性

如何去评价一个算法 正确性 有限时间计算 正确的答案 工作量 对于给定问题, 该算法所执行的基本运算的次数基本运算 : 比较 四则运算 置指针 平均情况 A(n) 和最坏情况 W(n) 占用空间 通常只考虑额外空间的占用, 占用常数额外空间称为原地工作算法 简单性

寻找最优算法的途径 设计一个算法 A, 求出算法 A 的 W(n), 得到算法类最坏情况下时间复杂度上界 寻找函数 F(n), 使得所有算法在规模为 n 的输入下至少要做 F(n) 次运算, 得到算法类最坏情况下时间复杂度下界 若 W(n)=F(n), 或者 W(n) 与 F(n) 同阶, 则 A 就是最优的 如果 W(n)>F(n), 则 A 不是最优的或者 F(n) 过低 改进算法 A, 改善上界 提高下界 F(n)

平凡下界 算法的输入和输出规模 写出所有 n 阶置换 :Ω(n!) 求 n 次实系数多项式在 x 的值 :Ω(n) 求两个 n 阶矩阵乘积 :Ω(n 2 ) 找最大算法 Findmax 已经达到平凡下界, 故是最优算法

决策树 二叉树, 内部结点代表一次运算 ( 比较 ), 内部结点或叶结点代表一个输出 任何算法得到输出必须完成由根结点到叶 ( 内部 ) 结点所在路径的所有运算, 计算的工作量恰好等于路径上的结点个数 给定一个算法, 对于不同的输入, 算法将在对应决策树的某个结点 ( 树叶或者内部结点 ) 停机 将该结点标记为输入 问题的输入规模对应于决策树的结点总数或者叶结点数

决策树与问题复杂度 结点数 ( 树叶数 ) 等于输入规模 最坏情况下的时间复杂度对应于决策树的深度 平均情况下的时间复杂度对应于决策树的平均路径长度

回顾二叉树的性质 在二叉树的 t 层至多 2 t 个结点 ( 根为 0 层 ) 深度为 d 的二叉树至多有 2 d+1 1 个结点 n 个结点的二叉树的深度至少为 logn 设 t 为二叉树的树叶个数,d 为树深, 如果树的每个内结点都有 2 个儿子, 则 t 2 d 归纳法 :t = t + x 2 2d 1 + 2 d 1 = 2 d

检索问题 给定按非递减顺序排列的数组 L( 项数 n>=1) 和数 x, 如果 x 在 L 中, 输出 x 的下标 ; 否则输出 0. 顺序检索算法 : 从 i=1 开始检索直到 x=l[i] 或 i>n 停止 时间复杂度 W(n) = n,a(n) 3n/4. 二分检索算法 : 通过二分确定 x 的位置 时间复杂度 W n = logn + 1,A n = 1 2n+1 (1S 1 + 2S 2 + + ks k ) logn + 1 2

检索问题的决策树 设 A 是一个检索算法, 对于给定输入规模 n,a 的一棵决策树是一棵二叉树, 其结点被标记为 1, 2,..., n, 且标记规则是 : 根据算法 A, 首先与 x 比较的 L 的项的下标标记为树根 假设某结点被标记为 i, i 的左儿子是 : 当 x<l(i) 时, 算法 A 下一步与 x 比较的项的下标 i 的右儿子是 : 当 x>l(i) 时, 算法 A 下一步与 x 比较的项的下标 若 x<l(i) 时算法 A 停止, 则不给 i 设置左儿子 若 x>l(i) 时算法 A 停止, 则不给 i 设置右儿子 若 x=l(i), 将该结点标记为输出结点, 则不给 i 设置儿子

检索问题的决策树 顺序检索算法和二分检索算法的决策树,n=15 对于有序表的检索问题, 在以比较为基本运算的算法类中, 二分法在最坏情况下是最优的

概要 第一部分检索 算法的评价指标 平凡下界 决策树与时间复杂度 第二部分排序 冒泡排序 堆排序等排序算法 排序算法的复杂度下界 第三部分选择 选择问题的时间复杂度分析 问题之间的归约性

冒泡排序 算法概括 : 两层循环, 内层循环不断交换逆序对并记录最后出现逆序对的位置 FLAG, 外层循环判断 FLAG 是否大于 1, 若大于 1, 则继续执行内层循环 最坏情况下时间复杂度 :W(n) = Θ(n 2 ) 分析平均情况下的时间复杂度 : 定义逆序序列 首先是 1 到 n 的一个排列 在数 i 右边, 并且小于数 i 的元素个数记作 b i, i = 1, 2,, n. 则 (b1, b2,, bn) 称为置换的逆序序列 总共 n! 个不同的逆序序列, 置换与逆序序列一一对应 序列的逆序对数就是 σ n i=1 b i.

冒泡排序 平均情况 : 设各种输入是等可能的, 置换 α 的逆序序列是 b1, b2,, bn, 置换 α 的逆序序列为 (0 b1, 1 b2,, n 1 bn), 也就是将 α 整个反过来构成 α. α 与 α n n 1 的逆序数之和为 n n 1 和为 2 n n 1 平均逆序数 4. 2. n! 个置换分成 n n 1, 平均的交换次数为 4 故冒泡排序的最坏和平均时间复杂度为 O(n 2 ). n! 2. 个组, 每组逆序之

堆排序 堆的定义 堆排序采用大根堆 堆的整理操作 : 从某个结点 i 开始, 向下递归调整, 容易证明向下调整时间复杂度为 O(h), 其中 h 是自底向上的高度 建堆算法 : 从 A[n/2] 到 A[1] 依次向下调整数组 logn 时间复杂度 :T n = σ h=0 高为 h 的结点数 O(h) 证明 n 个结点的堆恰好有 n/2 片树叶 归纳证明 n 个元素的堆高度 h 的层至多存在 n/2 h+1 个结点. logn 故 T n = σ h=0 n 2 h+1 O h = O n σ h=0 n 2 h+1 = O(n)

堆排序 算法概括 : 将数组 A 建好大根堆后, 把根中的元素与最大标号结点中的元素交换, 把这个元素从堆中删去, 得到规模减少 1 的堆结构, 对堆的根进行向下调整操作 不断执行上述操作直到堆的大小为 1 为之 时间复杂度 : 建堆 O(n),n 1 次调整, 每次复杂度 O(logn), 故最坏情况时间复杂度为 O(nlogn)

排序算法的决策树 任取算法 A, 输入 L={x1, x2,, xn}, 如下定义决策树 : 1. A 第一次比较的元素为 xi, xj, 那么树根标记为 i, j 2. 假设结点 k 已经标记为 i, j, (1) xi < xj 若算法结束,k 的左儿子标记为输入 ; 若下一步比较元素 xp, xq, 那么 k 的左儿子标记为 p,q (2) xi > xj 若算法结束,k 的右儿子标记为输入 ; 若下一步比较元素 xp, xq, 那么 k 的右儿子标记为 p,q

排序算法的决策树 设输入为 x1,x2,x3, 冒泡排序的决策树为 排序算法决策树的树叶数都等于 n!, 故最坏情况下时间复杂度不低于 log(n!), 近似为 nlogn 1.5n

排序算法的决策树 下面考虑平均情况下排序算法时间复杂度下界 epl(t) 表示从根到树叶所有路径长度之和, 总计 n! 个路径 证明树叶在两个相邻层上的树的 epl 值最小 :

排序算法平均时间下界 若决策树是一棵完全二叉树, 所有的树叶都在最底层, 树叶片数 t = 2 d, 则 epl(t) = td = t logt 若不是, 则

排序算法平均时间下界 故平均时间复杂度下界为

概要 第一部分检索 算法的评价指标 平凡下界 决策树与时间复杂度 第二部分排序 冒泡排序 堆排序等排序算法 排序算法的复杂度下界 第三部分选择 选择问题的时间复杂度分析 问题之间的归约性

选择问题最坏情况下时间复杂度

选择问题下界的证明方法 对任何解选择问题的算法 A, 通过构造算法 A 的最坏输入, 来证明问题的下界 如果某个算法 A 特别好, 那么对最坏输入的表现也会好, 此时 A 就是最优的算法 因此在最坏输入下的最好情况, 就是要找的问题的下界

选最大最小算法 FindMaxMin 算法概括 : 将 n 个数两个一组分成 n/2 组, 每组比较得到 n/2 个较小和 n/2 较大, 在 n/2 较小中找最小 min, 在 n/2 个较大中找最大 max 最坏情况下时间复杂度为 W n = n/2 + 2 n/2 2 = 3n 2 2 证明思路 : 任给算法 A, 根据算法 A 的比较过程构造最坏输入 T, 使得 3n A 对 T 至少做 2 次比较 2 信息单位 :W 表示赢,L 表示输, 共需要找到 2(n-2)+2=2n-2 个信息单位

构造最坏输入 根据算法的比较次序, 针对每一步参与比较的两个变量的状态, 调整对参与比较的两个变量的赋值, 使得每次比较后得到的信息单位数达到最小

选最大最小问题时间复杂度下界 一次比较得到 2 个信息单位只有 case1 A 至多有 n/2 个 case1, 至多得到 2 n/2 n 个信息单位 其它 case,1 次比较至多获得 1 个信息单位, 至少还需要 n-2 次比较 当 n 为偶数,A 做的比较次数至少为 n 2 + n 2 = 3n 2 2 = 3n 2 2 当 n 为奇数,A 做的比较次数至少为 n 2 n 1 + n 2 + 1 = + 1 + n 2 = 3n 2 2 2 结论 :FindMaxMin 是最优算法

找第二大算法 锦标赛算法概括 : 初始 k=n, 将 k 个元素两两分组比较, 找到较大的数, 将被淘汰较小的数在淘汰它的数所指向的链表中做记录, 然后 k= n/2, 直到剩下一个数 Max, 在 Max 所指向的链表中找最大的 Second 最坏情况时间复杂度为 W n = n 1 + logn 1 = n + logn 2 定义元素 x 的权 :w(x) 表示以 x 为根的子树中的结点数 初始 w(x) 都等于 1, 一旦元素比较后失败则赋值 0 1. w(x), w(y)>0: 若 w(x)>=w(y),w(x) w(x)+w(y), w(y) 0 // 权大者胜 若 w(x)<w(y),w(y) w(x)+w(y), w(x) 0 2. w(x)=w(y)=0, 那么 x, y 值不变 ; // 元素 x 与 y 比较对于确定第二大无意义

实例

构造树 类似于并查集合并的方式构造树 1. 初始是森林, 含有 n 个结点 ; 2. 如果 x, y 是子树的树根, 且算法比较 x, y; 若 x, y 以前没有参加过比较, 任意赋值给 x, y, 比如 x>y; 那么将 y 作为 x 的儿子 ; 若 x, y 已经在前面的比较中赋过值, 且 x>y, 那么把 y 作为 x 的儿子, 以 y 为根的子树作为 x 的子树 ;

实例

找第二大问题时间复杂度下界 根据上述规则, 赋值结束时根的权值是 n, 其他结点是 0 设 p(k) 表示最大元素通过 k 次比较后形成以它为根的子树的结点数, 假设第 k 次比较是最大元与 x 的比较, 则 p k 1 w(x), 而 p(k) = p(k 1) + w(x), 于是 p k 2p(k 1) 令 K 是算法运行时最大元与权不为 0 的结点的比较次数, 则 n = p k 2 K p 0 2 K K logn K logn 故在最坏输入下被最大元直接淘汰的元素至少为 logn 个 所以找第二大问题最坏情况下需要比较 n 1 + logn 1 = n + logn 2 次, 锦标赛算法是最优算法

找中位数问题 使用 Select 算法 证明 : 当 n 是奇数时, 任何通过比较运算找 n 个数的中位数的算法在最坏情况下至少要做 3n/2-3/2 次运算 决定性的比较 : 建立了 x 与 median 的关系的比较 y(x > y 且 y median),x 满足上述条件的第一次比较 y(x < y 且 y median),x 满足上述条件的第一次比较 非决定性的比较 : 当 x > median, y < median, 这时 x > y 的比较不是决定性的 为找到中位数, 必须要做 n 1 次决定性比较, 而非决定性比较的次数根据算法好坏决定, 下面通过构造最坏输入证明非决定性比较次数至少为 (n 1)/2 次

构造最坏输入 1. 分配一个值给中位数 median; 2. 如果 A 比较 x 与 y, 且 x 与 y 没有被赋值, 那么赋值 x,y 使得 x > median, y < median; 3. 如果 A 比较 x 与 y, 且 x > median, y 没被赋值, 则赋值 y 使得 y < median; 4. 如果 A 比较 x 与 y, 且 x < median, y 没被赋值, 则赋值 y 使得 y > median; 5. 如果存在 (n 1)/2 个元素已得到小于 median 的值, 则对未赋值的全部分配大于 median 的值 ; 6. 如果存在 (n 1)/2 个元素已得到大于 median 的值, 则对未赋值的全部分配小于 median 的值 ; 7. 如果剩下 1 个元素则分配 median 给它

找中位数问题时间复杂度下界 在上述赋值规则下, 直到对输入的赋值完成之前, 算法 A 所进行具有赋值比较都是非决定性的 这样的比较至少有 (n 1)/2 次 加上 n 1 次决定性比较, 算法 A 的比较次数至少为 n 1 + n 1 = 3n 2 2 3 2 Select 算法在阶上达到最优

问题之间的归约 问题 P, 问题 Q 问题 Q 的时间复杂度已知 ( 至少线性 ) Ω(g n ) 存在变换 f 将 Q 的任何实例转换成 P 的实例,f 的时间为线性 时间 f(n) = O(n), 解的反变换 s(n) 也是线性时间 解 Q 的算法 :Tq(n) = f(n) + Tp(n) + s(n) 所以解 P 的算法可以解 Q, 且时间的阶相同, 问题 Q 不比问题 P 简单,Q l P

质因数分解与素数测试 归约 test factor 素数测试算法 A(n) 假设 test 问题的复杂度是 W(n) 1. if n=1 then return No 2. else p factor(n) 3. if p >= 2 then return No 4. else return Yes 结论 :Ω W n T factor (n)

元素唯一性问题 问题 : 给定 n 个数的集合 S, 判断 S 中的元素是否存在相同元素 输入 : 多重集 S ={ n1*a1, n2*a2,, nk*ak } 构造决策树, 树叶为 S 的全排列数 n! n 1! n 2! n k! 最坏情况下树深为 Θ logn! = Θ(nlogn)

元素唯一性与最临近点对 待求的 P 问题 : 最临近点对 已知的 Q 问题 : 元素的唯一性 给定元素 x1,x2,,xn, 构造点 (x1,0), (x2,0),,(xn,0) 用最临近点对算法计算最短距离 d 如果 d=0, 则回答 No 如果 d>0, 则回答 Yes 由此可见 P 问题不比 Q 问题简单, 所有的 Q 问题都可以被 P 问题的算法求解, 所以 P 问题时间复杂度下界不会低于 Q 问题的 Ω(nlogn)

元素的唯一性与最小生成树 待求的 P 问题 : 最小生成树 已知的 Q 问题 : 元素的唯一性 给定元素 x1,x2,,xn, 构造点 (x1,0), (x2,0),,(xn,0) 利用最小生成树算法构造树 T, 求出最短边 e 如果 e>0, 则回答 Yes 如果 e=0, 则回答 No 由此可见 P 问题不比 Q 问题简单, 所有的 Q 问题都可以被 P 问题的算法求解, 所以 P 问题时间复杂度下界不会低于 Q 问题的 Ω(nlogn)

谢谢