知识库

算法分析-顺序算法分析方法

6分钟阅读

顺序算法分析的基本方法

原始文件: /田浩然上传的资料/0A002算法分析与设计/lecture9.pdf
文件大小: 395.85 KB
页数: 10页PPT
处理日期: 2026-08-31
处理方式: PDF文本提取

核心内容

这是一份北京大学算法分析与设计课程的教学幻灯片，系统介绍了算法分析的四大基本原则和方法论。

一、算法分析的四项基本原则

原则含义
正确性在给定有效输入后，算法经过有限时间计算产生正确答案
工作量（时间复杂度）对于给定问题，算法执行的基本运算次数 W(n)（最坏情况）或 A(n)（平均情况）
占用空间（空间复杂度）存储中间结果所需的额外空间
简单性算法和程序结构简单，便于验证正确性和调试

关键认识：简单的算法效率不一定高，要在保证一定效率的前提下力求简单。

二、最优性概念

  • 最坏情况下最优：不存在其他算法在最坏情况下的时间复杂度比它更低
  • 平均情况下最优：不存在其他算法在平均情况下的时间复杂度比它更低

寻找最优算法的途径：

  1. 设计算法 A，求 W(n)（给出上界）
  2. 寻找函数 F(n)，证明任何算法在最坏情况下至少要做 F(n) 次基本运算（下界）
  3. 若 W(n) = F(n)，则 A 是最优的

三、下界证明的三种方法

方法1：判定树法

  • 判定树：算法类的模型，每个结点对应一次比较
  • 树深代表最坏情况工作量，平均路径长度代表平均工作量
  • 应用：证明二分搜索最坏情况复杂度下界为 ⌊log n⌋ + 1

关键引理：

  • 深度为 d 的二叉树至多有 2^(d+1) - 1 个结点
  • n 个结点的二叉树深度至少为 ⌊log n⌋
  • 对任何搜索算法，存在规模为 n 的输入使其至少做 ⌊log n⌋ + 1 次比较

结论：二分搜索在最坏情况下是最优算法。

方法2：构造最坏输入

  • 将算法操作序列分为两类：决定性操作（提供有效信息）和非决定性操作（冗余）
  • 构造输入实例，使冗余操作尽可能多
  • 给出冗余操作 + 必要操作的计数公式

方法3：归约

  • 已知问题 Q 的最坏情况时间复杂度下界为 F(n)
  • 设计解 Q 的算法 A，调用任意解 P 的算法 B（复杂度 p(n)）
  • 若转换时间为 t₁(n) + t₂(n) = O(p(n))，则 T(n) = Θ(p(n)) = Ω(F(n))
  • 结论：P 至少与 Q 一样难

四、典型算法实例分析

搜索有序表

算法最坏复杂度平均复杂度
顺序搜索W(n) = nA(n) ≈ 3n/4
二分搜索W(n) = ⌊log n⌋ + 1A(n) ≈ ⌊log n⌋ - 1

顺序搜索改进：在表尾添加哨兵 x，可免去每步循环的边界检查，速度提高约 25%。

排序算法复杂度对比

算法最坏情况平均情况
快速排序O(n²)O(n log n)
二分归并排序O(n log n)O(n log n)
堆排序O(n log n)O(n log n)

堆排序详细分析

  • 堆定义：完全二叉树，每个结点元素不小于其子结点元素
  • HEAPIFY(A, i)：维持堆性质，复杂度 Θ(log n)（子堆大小至多为原树的 2/3）
  • BUILD-HEAP(A)：自底向上建堆，复杂度 O(n)
  • 堆排序：反复删除最大元素并重建堆，复杂度 O(n log n)

关键结论

  1. 二分搜索是最优搜索算法：通过判定树法证明任何基于比较的搜索算法都需要至少 ⌊log n⌋ + 1 次比较
  2. 堆排序稳定达到 O(n log n)：相比快速排序，堆排序在最坏情况下仍能保持对数级别复杂度
  3. 下界证明是验证最优性的核心工具：三种方法（判定树、构造最坏输入、归约）各有适用场景

与其他知识关联

关系图谱