问题复杂度

1 算法评价指标¶

1.1 正确性¶

正确性 指在给定有效输入后，算法经过有限时间的计算并产生正确的答案。

正确性证明包含两部分：

• 方法的正确性证明 —— 算法思路的正确性，证明一系列与算法工作对象有关的引理、定理以及公式
• 程序的正确性证明 —— 证明所给出的一系列指令确实做了所要求的工作

1.2 工作量与时间复杂性¶

计量工作量的标准：对于给定问题，该算法所执行的基本运算的次数。

基本运算的选择 根据问题选择适当的基本运算：

两种时间复杂性：

• 最坏情况下的复杂性 \(W(n)\)
• 平均情况下的复杂性 \(A(n)\)

1.3 空间复杂性¶

两种占用：

• 存储程序和输入数据的空间
• 存储中间结果或操作单元所占用空间 —— 额外空间

影响空间的主要因素：

• 存储程序的空间一般是常数（和输入规模无关）
• 输入数据空间为输入规模 \(O(n)\)
• 空间复杂性考虑的是 额外空间 的大小

额外空间相对于输入规模是常数，称为 原地工作 的算法。

1.4 简单性¶

含义：算法简单，程序结构简单。

好处：

• 容易验证正确性
• 便于程序调试

1.5 基于时间的最优性¶

含义：指求解某问题算法类中效率最高的算法。

两种最优性：

• 最坏情况下最优：设 \(A\) 是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比 \(A\) 在最坏情况下的时间复杂性低，则称 \(A\) 是解这个问题在最坏情况下的最优算法。
• 平均情况下最优：设 \(A\) 是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比 \(A\) 在平均情况下的时间复杂性低，则称 \(A\) 是解这个问题在平均情况下的最优算法。

1.6 寻找最优算法的途径¶

1. 设计算法 \(A\)，求 \(W(n)\)，得到算法类最坏情况下时间复杂度的一个 上界
2. 寻找函数 \(F(n)\)，使得对任何算法都存在一个规模为 \(n\) 的输入并且该算法在这个输入下至少要做 \(F(n)\) 次基本运算，得到该算法类最坏情况下时间复杂度的一个 下界
3. 如果 \(W(n) = F(n)\) 或 \(W(n) = \Theta(F(n))\)，则 \(A\) 是最优的
4. 如果 \(W(n) > F(n)\)，\(A\) 不是最优的或者 \(F(n)\) 的下界过低

改进 \(A\) 或设计新算法 \(A'\) 使得 \(W'(n) < W(n)\)，重新证明新下界 \(F'(n)\) 使得 \(F'(n) > F(n)\)。重复以上两步，最终得到 \(W'(n) = F'(n)\) 或者 \(W'(n) = \Theta(F'(n))\)。

2 平凡下界与直接计算最少运算次数¶

2.1 平凡下界¶

算法的输入规模和输出规模是它的平凡下界。

2.2 直接计数最少运算数¶

3 决策树模型¶

3.1 决策树的定义¶

决策树 是一棵二叉树，对于给定问题（以比较运算作为基本运算）规定一个决策树的构造规则。求解这个问题的不同算法所构造的决策树结构不一样。

给定一个算法的决策树：

• 对于任何输入实例，算法将从树根开始，沿一条路径向下
• 在每个结点做一次基本操作（比较）
• 然后根据比较结果（\(<, =, >\)）走到某个儿子结点或者在该处停机
• 对于给定实例的计算恰好对应了一条从树根到树叶或者某个内部结点的路径

3.2 决策树与问题复杂度¶

决策树的特点：

• 以比较作基本运算的算法模型
• 一个问题确定了一类决策树，具有相同的构造规则，该决策树类决定了求解该问题的一个算法类
• 决策树规模由问题的可区分情形决定，不一定等于输入规模
• 对有序表检索，可用 \(n\) 个内部比较结点表示 \(n\) 个表项，失败情形对应 \(n+1\) 个外部空隙
• 对比较排序，树叶至少要覆盖 \(n!\) 种可能输出
• 最坏情况下的时间复杂度对应于决策树的 深度
• 平均情况下的时间复杂度对应于决策树的 平均路径长度

用决策树模型界定确定问题难度：

• 给定结点数（或树叶数）的决策树的深度至少是多少？
• 给定结点数（或树叶数）的决策树的平均路径长度至少是多少？

3.3 二叉树的性质¶

4 检索问题的时间复杂度分析¶

4.1 顺序检索¶

算法：顺序检索¶

输入：数组 \(L\)，元素个数 \(n\)，待查元素 \(x\)

输出：\(x\) 在 \(L\) 中的下标 \(j\)，若不存在则返回 \(0\)

分析：设 \(x\) 在 \(L\) 中每个位置和空隙的概率都是 \(1/(2n+1)\)

4.2 二分检索¶

最坏情况时间复杂度：

平均情况时间复杂度：

令 \(n = 2^k - 1\)，\(S_t\) 是算法做 \(t\) 次比较的输入个数，\(1 \leq t \leq k\)。

4.3 检索问题的决策树¶

设 \(A\) 是一个检索算法，对于给定输入规模 \(n\)，\(A\) 的一棵决策树是一棵二叉树，其结点被标记为 \(1, 2, \ldots, 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\) 没有右儿子

5 排序问题的时间复杂度分析¶

5.1 冒泡排序¶

算法：冒泡排序¶

输入：数组 \(L\)，项数 \(n \geq 1\)

输出：按非递减顺序排序的 \(L\)

特点：交换发生在相邻元素之间。

5.1.1 置换与逆序¶

• 逆序：在置换 \(a_1 a_2 \ldots a_n\) 中，若 \(i < j\) 但 \(a_i > a_j\)，则称 \((a_i, a_j)\) 为该置换的一个逆序
• 逆序序列：在 \(i\) 右边并且小于 \(i\) 的元素个数记作 \(b_i\)，\(i = 1, 2, \ldots, n\)。\((b_1, b_2, \ldots, b_n)\) 称为置换的逆序序列
• 性质：\(b_1 = 0\)；\(b_2 = 0, 1\)；\(\ldots\)；\(b_n = 0, 1, \ldots, n-1\)
• 总共 \(n!\) 个不同的逆序序列，置换与逆序序列一一对应
• 逆序数：置换中的逆序总数 \(b_1 + b_2 + \cdots + b_n\)

5.1.2 复杂度分析¶

• 最坏情况：\(W(n) = O(n^2)\)，至多巡回 \(O(n)\) 次，每次 \(O(n)\)
• 对换只发生在相邻元素之间，每次相邻元素交换只消除1个逆序，比较次数不少于逆序数，最大逆序数 \(n(n-1)/2\)，于是 \(W(n) = \Omega(n^2)\)
• 平均情况：设各种输入是等可能的，\(n!\) 个置换分成 \(n!/2\) 个组，每组逆序之和为 \(n(n-1)/2\)。平均逆序数 \(n(n-1)/4\)，平均的交换次数为 \(n(n-1)/4\)

5.2 堆排序¶

5.2.1 堆的定义¶

设 \(T\) 是一棵深度为 \(d\) 的二叉树，结点为 \(L\) 中的元素。若满足以下条件，称作 堆：

1. 所有内结点（可能一点除外）的度数为 2
2. 所有树叶至多在相邻的两层
3. \(d-1\) 层的所有树叶在内结点的右边
4. \(d-1\) 层最右边的内结点可能度数为1（没有右儿子）
5. 每个结点的元素不小于儿子的元素

若只满足前4条，不满足第5条，称作 堆结构。

5.2.2 堆的运算：整理 Heapify¶

算法：Heapify¶

输入：数组 \(A\)，结点下标 \(i\)

输出：以 \(i\) 为根的子树满足堆性质

复杂度分析：

• 每次调用为 \(O(1)\)
• 子堆大小至多为原来的 \(2/3\)
• 递推不等式：\(T(n) \leq T(2n/3) + \theta(1)\)
• 解得 \(T(n) = \theta(\log n)\)，或 \(T(h) = \theta(h)\)（\(h\) 为堆的根的高度）

5.2.3 建堆时间复杂度¶

算法：Build-Heap¶

由此可得建堆时间复杂度为 \(O(n)\)。

5.3 排序算法的复杂度下界¶

5.3.1 外部路径长度¶

设 \(T\) 是一棵 \(B\) 树（每个内结点有2个儿子），\(t\) 片树叶，\(d\) 为树深。

外部路径长度 \(epl(T)\)：从根到每片树叶的路径长度之和。

5.3.2 平均复杂度的下界¶

5.3.3 几种排序算法的比较¶

6 构造最坏输入¶

6.1 方法概述¶

下界证明方法：构造最坏输入

• 任意给定一个算法 \(A\)，\(A\) 对于任意输入 \(x\) 都存在一个确定的操作序列 \(t\)
• \(t\) 中的操作分成两类：
  • 决定性的：能够对确定输出结果提供有效信息
  • 非决定性的：对确定结果没有帮助的冗余操作
• 根据算法 \(A\) 构造某个输入实例 \(x\)，使得 \(A\) 对 \(x\) 的操作序列 \(t\) 包含尽量多的非决定性操作
• 给出冗余操作 + 必要的操作的计数公式

6.2 选择算法的有关结果¶

6.3 选最大与最小算法¶

6.3.1 数的状态标记¶

如果比较后数的状态改变，则提供信息单位：

• 每增加1个 \(W\) 提供1个信息单位
• 每增加1个 \(L\) 提供1个信息单位

算法能够输出最大值和最小值的条件是：\(n-2\) 个数同时带有 \(W\) 和 \(L\) 标记，最大数只带 \(W\) 标记，最小数只带 \(L\) 标记，总计需要 \(2n-2\) 个信息单位。

针对任意算法，可按算法的比较次序构造输入，使每次比较得到的信息单位尽量少：

6.3.2 下界证明¶

为得到 \(2n-2\) 个信息单位，对上述输入 \(A\) 至少做 \(\lceil 3n/2 \rceil - 2\) 次比较。

• 一次比较得到2个信息单位只有 Case 1。\(A\) 至多有 \(\lfloor n/2 \rfloor\) 个 Case 1，至多得到 \(2\lfloor n/2 \rfloor \leq n\) 个信息单位
• 其它 Case，1次比较至多获得1个信息单位，至少还需要 \(n-2\) 次比较

当 \(n\) 为偶数：

当 \(n\) 为奇数：

6.4 找第二大问题¶

元素 \(x\) 的权 \(w(x)\)：表示以 \(x\) 为根的子树中的结点数。

• 初始：\(w(x_i) = 1\)，\(i = 1, 2, \ldots, n\)
• 赋值原则：在比较的时候进行赋值或者调整赋值。只对没有失败过的元素（权大于0的元素）进行赋值。权大者胜，原来胜的次数多的仍旧胜，输入值也大
  • 若 \(w(x), w(y) > 0\) 且 \(w(x) > w(y)\)，令 \(x > y\)
  • 若 \(w(x), w(y) > 0\) 且 \(w(x) = w(y)\)，可任意指定胜者，例如令 \(x > y\)
  • 若 \(w(x) = w(y) = 0\)，保持 \(x, y\) 的值不变，这次比较对确定第二大没有帮助

6.4.1 构造树¶

根据算法 \(A\) 的比较次序，在比最大的过程中如下构造树：

1. 初始是森林，含有 \(n\) 个结点
2. 如果 \(x, y\) 是子树的树根，则算法比较 \(x, y\)
3. 若 \(x, y\) 以前没有参加过比较，任意赋值给 \(x, y\)，比如 \(x > y\)；那么将 \(y\) 作为 \(x\) 的儿子
4. 若 \(x, y\) 已经在前面的比较中赋过值，且 \(w(x) > w(y)\)，那么把 \(y\) 作为 \(x\) 的儿子，以 \(y\) 为根的子树作为 \(x\) 的子树
5. 比较后胜者的权变为两棵子树权之和，败者的权变为 \(0\)

6.4.2 复杂度下界¶

针对构造出的输入，最终根为 \(max\)，根的权为 \(n\)，其它结点权为 \(0\)。第二大元素一定在直接与 \(max\) 比较并被淘汰的元素中。

设 \(w_k\) 表示 \(max\) 在第 \(k\) 次与权不为 \(0\) 的结点比较后，以 \(max\) 为根的子树结点总数。因为每次按“权大者胜”构造，故：

设 \(K\) 为 \(max\) 最终与权不为 \(0\) 的结点比较的次数，则：

因此：

这 \(K\) 个直接输给 \(max\) 的元素彼此不同。为了确定第二大，需要在它们中再淘汰 \(K-1\) 个元素，至少还需要 \(\lceil \log n \rceil - 1\) 次比较。于是找第二大的最坏情况比较次数至少为：

6.5 找中位数与第 \(k\) 小问题¶

6.5.1 找中位数下界¶

将比较分为两类：

• 决定性的比较：第一次建立某个元素 \(x\) 与中位数关系的比较
  • 若存在 \(y\)，使 \(x > y\) 且 \(y \geq median\)，则可确定 \(x > median\)
  • 若存在 \(y\)，使 \(x < y\) 且 \(y \leq median\)，则可确定 \(x < median\)
• 非决定性的比较：若实际有 \(x > median\)、\(y < median\)，比较 \(x > y\) 并不能确定二者分别位于中位数哪一侧

为找到中位数，除中位数本身外的 \(n-1\) 个元素都必须被确定在中位数的某一侧，因此必须做 \(n-1\) 次决定性比较。

6.5.2 输入构造与分析¶

元素状态：

构造输入时，按算法 \(A\) 的比较次序赋值：

1. 先分配一个值给中位数 \(median\)
2. 若 \(A\) 比较 \(x\) 与 \(y\)，且 \(x, y\) 均未赋值，则令一个大于 \(median\)，另一个小于 \(median\)
3. 若 \(A\) 比较 \(x\) 与 \(y\)，且 \(x > median\)、\(y\) 未赋值，则令 \(y < median\)
4. 若 \(A\) 比较 \(x\) 与 \(y\)，且 \(x < median\)、\(y\) 未赋值，则令 \(y > median\)
5. 若已有 \((n-1)/2\) 个元素小于 \(median\)，则将未赋值元素全部分配为大于 \(median\)
6. 若已有 \((n-1)/2\) 个元素大于 \(median\)，则将未赋值元素全部分配为小于 \(median\)
7. 若最后只剩下1个元素，则把它分配为 \(median\)

这样构造出的输入使算法至少经历 \((n-1)/2\) 次非决定性比较。因此总比较次数至少为：

6.5.3 找第 \(k\) 小问题¶

任意通过比较找第 \(k\) 小元素的问题下界为：

Select 算法最坏情况为 \(O(n)\)，因此找第 \(k\) 小在阶上达到最优。

6.6 问题归约方法¶

设问题 \(Q\) 的复杂度下界已知为 \(\Omega(g(n))\)，且 \(g(n)\) 至少是线性的。若存在一个线性时间变换 \(f\)，能把 \(Q\) 的任意实例转换成问题 \(P\) 的实例，并且解的反变换 \(s\) 也是线性时间，则可用求解 \(P\) 的算法作为子程序求解 \(Q\)：

1. 将 \(Q\) 的实例 \(I\) 变成 \(f(I)\)，耗时 \(O(n)\)
2. 用解 \(P\) 的算法求解 \(f(I)\)，耗时 \(T_P(n)\)
3. 将结果变换成原问题 \(Q\) 的解，耗时 \(O(n)\)

于是：

因此，若记 \(Q \leq_l P\)（线性时间归约），则 \(P\) 至少与 \(Q\) 一样难：

6.6.1 素数测试与因数分解¶

• 素数测试 \(test_p\)：输入正整数 \(n\)，\(test(n)\) 为 "Yes" 或者 "No"
• 归约：\(test_p \leq factor\)
• 假设 \(test_p\) 问题的难度是 \(W(n)\)

算法：PrimeTest¶

• 结论：一次因数分解调用即可完成素数测试，故

若素数测试的下界为 \(\Omega(W(n))\)，则：

6.6.2 元素唯一性问题¶

问题：给定 \(n\) 个数构成的序列或多重集 \(S\)，判断 \(S\) 中是否存在相同元素。

• 元素唯一性问题的复杂度为 \(\Theta(n \log n)\)
• 输入：多重集 \(S = \{ n_1 \times a_1, n_2 \times a_2, \ldots, n_k \times a_k \}\)
• 构造决策树，树叶为 \(S\) 的全排列数：

• 最坏情况下所有元素互异，树叶数为 \(n!\)，树深至少为：

• 排序后线性扫描可以在 \(O(n \log n)\) 时间内解决该问题，因此上下界相同

6.6.3 最邻近点对与唯一性问题¶

• \(P\) 问题：平面直角坐标系中 \(n\) 个点的最邻近点对问题 \(Close\)
• \(Q\) 问题：元素的唯一性问题 \(Uniqueness\)，\(W(n) = \Omega(n \log n)\)
• 变换 \(f\)：\(Q\) 的实例 \(x_1, x_2, \ldots, x_n\)，变成点 \((x_1, 0), (x_2, 0), \ldots, (x_n, 0)\)

• 结论：计算平面直角坐标系中 \(n\) 个点的最邻近点对问题的时间是 \(\Omega(n \log n)\)，其中算法以比较为基本运算

6.6.4 最小生成树与唯一性问题¶

• \(P\) 问题：平面直角坐标系中 \(n\) 个点的最小生成树问题
• \(Q\) 问题：元素的唯一性问题 \(Uniqueness\)，\(W(n) = \Omega(n \log n)\)
• 变换 \(f\)：\(Q\) 的实例 \(x_1, x_2, \ldots, x_n\)，变成 \(X\) 轴上的 \(n\) 个点

• 结论：计算平面直角坐标系 \(n\) 点最小生成树时间是 \(\Omega(n \log n)\)，其中算法以比较为基本运算

7 总结¶