决策树模型 一种复杂度下界分析方法

_xm_ · 2026-01-28 20:46:34 · 算法·理论

“基于比较的排序，最坏需要进行 \Theta(n\log n) 次比较。”

相信大多数人在初学算法时都听过这句话，很早就把它当作常识记住了。本文将介绍证明该结论的一种方法——决策树模型。

1. 比较排序

定理：基于比较的排序最坏需要进行 \Theta(n \log n) 次比较。

问题描述

基于比较的排序算法是这样一类算法：

给定一个长度为 n 的序列 a，算法只能通过一种询问方式 \operatorname{comp}(i, j) 来判断命题 a_i \le a_j 是否成立。

算法的目标是输出一个排列 p，使得序列 a_{p_1}, a_{p_2}, \dots, a_{p_n} 按非降序排列。

复杂度下界分析

我们将 “确定排列 p 的过程” 视为一个黑盒。在算法开始时，我们对最终得到的排列 p 没有任何先验信息，它可能是 n! 种排列中的任意一种。

算法唯一允许的操作是进行一次比较 \operatorname{comp}(i, j)，以判断命题 a_i \le a_j 的真假。一次比较会产生两种可能的结果，并据此对所有可能的排列进行划分：

• 若 [a_i \le a_j] = \text{true}，则在最终排列中必有 p_i \le p_j；
• 若 [a_i \le a_j] = \text{false}，则必有 p_i > p_j。

也就是说，每一次比较都会将当前仍然可能的排列集合划分为两部分（某一部分也可能为空），而真正的答案排列一定落在其中的一部分中。

我们可以将上述过程抽象为一个 决策树：

• 决策树的每个节点对应一个排列集合，表示在当前已知比较结果下仍可能成为答案的排列；

• 根节点对应所有 n! 个排列组成的集合；

• 每进行一次比较，当前节点至多分裂为两个子节点，对应比较结果的两种可能；

• 无法继续划分等价类即为叶节点，在该节点上，所有仍可能的排列都对应同一个合法输出。

由于不同叶节点对应的排列集合两两无交，而排列总数为 n!，因此决策树的叶节点数不超过 n!。

决策树是一棵二叉树。对于高度为 h 的二叉树，其叶节点数至多为 2^h，于是有

因此，任何基于比较的排序算法最坏情况都至少需要 \Theta(\log_2(n!)) 次比较。

利用 Stirling 公式

可以得到

综上所述，任何基于比较的排序算法，最坏需要 \Theta(n \log n) 次比较。

另一方面，归并排序、堆排序等经典算法在最坏情况下均能在 O(n \log n) 次比较内完成排序。因此，这一下界在渐进意义下是紧的。

2. k 路归并

定理：基于比较的 k 路归并最坏需要进行 \Theta(N \log k) 次比较。

问题描述

给定 k 个有序数组 a_1, \cdots, a_k，第 i 个数组长度为 n_i，总长度为 N = \sum_{i = 1}^k n_i，现在要将其归并为一个有序序列。

算法

容易想到一个简单的算法，仿照 k = 2 时的双指针做法，每个数组维护一个指针，每次都选择指针中最小的放入答案序列，然后移动指针。这个过程可以通过一个大小为 k 的堆维护，时间复杂度 O(N \log k)。

可能有的同学对这个复杂度不够满意，希望通过更巧妙的方法进一步降低复杂度，那么问题来了：是否存在比 O(N \log k) 更快的基于比较的 k 路归并算法呢？

答案是 O(N \log k) 已经是最优的时间复杂度了，下面给出证明。

复杂度下界分析

这里可以套用上面的决策树模型，但不同的是我们这次有先验信息：每个数组内部顺序是已知的。

在保持每个数组内部相对顺序不变的前提下，把它们合并成一个序列的方案数，这就是多重集的全排列：

这就是该决策树的叶子节点数上界，由上例比较排序的分析可得树高 h \ge \log_2 \left(\frac{N!}{n_1!n_2!\cdots n_k!}\right)。

化简得

求上界，则 \sum n_i \log n_i 应该取最小值，现在变为求问题：

有 x_1 + x_2 + \cdots + x_k = n，已知 f(x) 为凸函数，求 \min f(x_1) + \cdots + f(x_k)。

根据琴生不等式，当 x_1 = x_2 = \cdots = x_k = \frac{n}{k} 时，f(x_1) + \cdots + f(x_k) 取最小值。

于是

综上，k 路归并的时间复杂度下界是 O(N \log k)。