算法、正确性与复杂度

Views: --

算法课并不只是“会写代码”。它真正研究的是：怎样把一个问题写成明确的计算过程，证明这个过程一定给出正确答案，并估计它需要多少资源。

1. 什么才算算法

一个算法至少应具备：

  • 输入：零个或多个外部给定量；
  • 输出：一个或多个与输入相关的结果；
  • 确定性：每一步的含义清楚，没有“适当处理一下”之类无法执行的描述；
  • 有限性：对合法输入能在有限步内结束；
  • 有效性：每一步都能由基本操作实现。

“问题”描述输入和期望输出之间的关系，“算法”给出如何从输入得到输出。一个问题可能有很多算法，课程的任务就是比较它们。

2. 从程序中抽出算法

课件常用伪代码，是因为具体语言会带来不必要的细节。以插入排序为例：

for j = 2 .. n:
    key = A[j]
    i = j - 1
    while i >= 1 and A[i] > key:
        A[i + 1] = A[i]
        i -= 1
    A[i + 1] = key

它维护一个已经排好序的前缀，把下一个元素插入正确位置。这里最重要的不是语法，而是“有序前缀”这个结构。

3. 如何证明算法正确

3.1 循环不变式

循环不变式是在每轮循环开始或结束时都成立的命题。证明通常有三步：

  1. 初始化：第一次循环前成立；
  2. 保持：若本轮开始时成立，执行一轮后仍成立；
  3. 终止：循环结束时，不变式与终止条件共同推出目标结论。

对插入排序，不变式可以写成：

每次外层循环开始时，A[1..j−1]A[1..j-1] 已按非降序排列，且包含原数组对应前缀的全部元素。

当 j=n+1j=n+1 时，前缀就是整个数组，所以排序正确。

3.2 递归算法

递归算法常用数学归纳法：

  • 基础规模直接正确；
  • 假设所有更小规模都正确；
  • 证明当前规模对子问题的调用正确，并且合并步骤能得到原问题答案。

这和分治算法的“分、治、合”正好对应。

4. RAM 计算模型

复杂度分析通常采用 RAM 模型，把以下操作近似视为常数时间：

  • 读取或写入一个内存单元；
  • 整数加减、比较、赋值；
  • 数组按下标访问；
  • 条件跳转。

这是抽象，不是说真实机器上所有操作完全一样快。它的意义是屏蔽 CPU、编译器和语言差异，保留随输入规模增长的主导规律。

若整数位数本身会随输入增长，乘法等操作不能永远算 O(1)O(1)。基础课程通常默认数值能放进机器字，除非题目专门讨论大整数。

5. 输入规模是什么

复杂度里的 nn 必须先定义：

  • 排序问题中，nn 是元素个数；
  • 图问题中，通常同时使用 VV 和 EE；
  • 矩阵问题中，n×nn\times n 矩阵有 n2n^2 个元素；
  • 数值问题中，输入整数 NN 的编码长度是 Θ(log⁡N)\Theta(\log N)，不是 NN。

如果连输入规模都没说清，复杂度结论往往没有意义。

6. 最好、平均与最坏情况

以插入排序为例：

  • 已排序数组：内层循环每次只比较一次，Θ(n)\Theta(n)；
  • 逆序数组：第 jj 轮移动 j−1j-1 个元素，总计 Θ(n2)\Theta(n^2)；
  • 随机排列：平均仍有常数比例的前序元素大于当前元素，所以是 Θ(n2)\Theta(n^2)。

算法分析最常报告最坏情况，因为它给出确定上界，不依赖输入分布。平均复杂度必须先说明“平均”所依据的概率分布。

7. 时间与空间

时间复杂度统计基本操作次数随输入规模的增长。空间复杂度要区分：

  • 输入本身占用的空间；
  • 算法额外申请的辅助空间；
  • 递归调用栈。

归并排序需要 O(n)O(n) 辅助数组；递归深度为 O(log⁡n)O(\log n)。快速排序虽然常被称为原地排序，递归栈仍会占空间，最坏可达 O(n)O(n)。

8. 算法设计的基本路线

后续课件反复使用几种范式：

  • 分治：把问题拆成独立子问题，再合并；
  • 动态规划：子问题重叠，保存状态避免重复计算；
  • 贪心：每一步做局部最优选择，并证明不会错失全局最优；
  • 图算法：利用连通、路径、树、流等结构；
  • 归约：把问题变成一个已经会解决的问题，或比较两个问题的难度。

真正的分界线不是代码长短，而是你有没有找对问题结构。

9. 自检清单

分析一个算法时依次回答：

  1. 输入规模是什么？
  2. 算法会终止吗？
  3. 为什么输出正确？不变式或归纳假设是什么？
  4. 哪个操作执行次数最多？
  5. 讨论的是最好、平均还是最坏情况？
  6. 是否遗漏递归栈和辅助数组？

评论