Skip to content

第一章 - 算法分析

约 936 个字 13 行代码 预计阅读时间 3 分钟

算法和程序

算法 (algorithm) 是为求解一个问题需要遵循的、被清楚地指定的有限个简单指令的集合。进一步说，一个算法必须满足以下条件：

  • 输入 (input)：存在零个或多个由外部提供的数值。
  • 输出 (output)：至少生成一个数值。
  • 确定性 (definiteness)：算法中的每条指令都是清晰、无歧义的。
  • 有限性 (finiteness)：对于所有可能的输入，算法都应该在有限步后停止。
  • 有效性 (effectiveness)：每条指令都应该是有效的，即能够通过纸笔、机器等物质执行。

程序 (programme)：程序是由某种程序设计语言编写，用于指示设备每一步动作的一组指令。

Note

算法必须是有限的，但程序可以不是有限的。比如一个操作系统能产生的状态就是无限的。

要分析的问题

一般地，要分析的最重要的资源是运行时间。一方面，运行时间和使用的编译器和计算机有关，但这不在理论模型分析的范畴内。因此我们分析的往往是另一方面，即算法的时间复杂度 (time complexities) 和空间复杂度 (space complexities)，这两者是与使用的编译器和计算机无关的。

对算法时间复杂度的分析基于如下几条假设：

  • 指令按顺序进行
  • 每条指令都是简单的，只花费一个单位时间执行
  • 运行的内存是无限的

通常算法的具体运行时间和输入的大小有关。我们定义两个函数 \(T_{\text{avg} (N)}\) 和 \(T_{\text{worst} (N)}\)，分别是输入为 \(N\) 时算法所花费的平均运行时间和最坏情况下的运行时间。如果存在更多的输入，那么这两个函数可以有更多的变量。

一般地，我们更重视分析最坏情况下的运行时间。因为这个分析为算法的时间复杂度提供了所有情况下的上限。另一方面，在许多算法中，「平均」的含义并不确切。如何定义「平均」可能影响分析的结果。

渐进符号

计算复杂度的目的是为了预测运行时间在 \(N\) 变化时的增长速率，从而比较两个程序的时间复杂度。所以关键在于 \(T\) 的渐近情况，为此我们要引入渐进符号 (asymptotic notation)。

\(O\) 符号

\(T(N) = O(f(N))\) 当且仅当 \(\exists c, n_{0}\)，使得 \(\forall N \geq n_{0}, T(N) \leq c \cdot f(N)\)。

\(O\) 符号表示复杂度的渐进上界。

\(\Omega\) 符号

\(T(N) = \Omega(f(N))\) 当且仅当 \(\exists c, n_{0}\)，使得 \(\forall N \geq n_{0}, T(N) \geq c \cdot f(N)\)。

\(\Omega\) 符号表示复杂度的渐进下界。

\(\Theta\) 符号

\(T(N) = \Theta(f(N))\) 当且仅当 \(T(N) = O(f(N))\) 且 \(T(N) = \Omega(f(N))\)。

\(\Theta\) 符号同时表示复杂度的渐进上界和渐进下界。换言之，\(\Theta\) 符号给出了算法复杂度精确的阶。

\(o\) 符号

\(T(N) = o(f(N))\) 当且仅当 \(T(N) = O(f(N))\) 且 \(T(N) \neq \Theta(f(N))\)。

即 \(\exists c, n_{0}\)，使得 \(\forall N \geq n_{0}, T(N) < c \cdot f(N)\)。

\(o\) 符号表示复杂度的严格渐进上界。

基本性质

渐近计算有如下几个基本性质：

  • 若 \(T_{1}(N) = O(f(N)), T_{2}(N) = O(g(N))\)，则
    • \(T_{1}(N) + T_{2}(N) = \max \{ O(f(N)), O(g(N)) \}\)
    • \(T_{1}(N) \cdot T_{2}(N) = O(f(N) \cdot g(N))\)
  • 若 \(T(N)\) 是一个 \(k\) 次多项式，则 \(T(N) = \Theta (N^{k})\)
  • 对任意常数 \(k\)，\((\log N)^{k} = O(N)\)

一般分析方法

for 循环

一次 for 循环的运行时间至多是该 for 循环内语句的运行时间乘以循环的次数。

嵌套的 for 循环

从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有 for 循环的大小的乘积。

举例来说，下列程序片段的时间复杂度为 \(O(N^{2})\):

for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
       k++;
    }
}

顺序语句

将各个语句的运行时间求和即可。

举例来说，下面的程序片段先花费 \(O(N)\)，再花费 \(O(N^{2})\)，总的时间复杂度也是 \(O(N^{2})\)：

for (i = 0; i < N; i++) {
    A[i] = 0;
}
for (i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        A[i] += A[j] + i + j;
    }
}

if/else 语句

if/else 语句的运行时间上界为完成判断的时间加上 if 分支与 else 分支中运行时间的较长者。