专栏文章

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

__xm_
算法·理论参与者 6已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mlia5wxw
此快照首次捕获于
2026/02/12 01:05
上周
此快照最后确认于
2026/02/19 01:13
16 小时前
查看原文
“基于比较的排序，最坏需要进行 Θ(nlog⁡n)\Theta(n\log n) 次比较。”
相信大多数人在初学算法时都听过这句话，很早就把它当作常识记住了。本文将介绍证明该结论的一种方法——决策树模型。

1. 比较排序

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

问题描述

基于比较的排序算法是这样一类算法：
给定一个长度为 nn 的序列 aa，算法只能通过一种询问方式 comp⁡(i,j)\operatorname{comp}(i, j) 来判断命题 ai≤aja_i \le a_j 是否成立。
算法的目标是输出一个排列 pp，使得序列 ap1,ap2,…,apna_{p_1}, a_{p_2}, \dots, a_{p_n} 按非降序排列。

复杂度下界分析

我们将 “确定排列 pp 的过程” 视为一个黑盒。在算法开始时，我们对最终得到的排列 pp 没有任何先验信息，它可能是 n!n! 种排列中的任意一种。
算法唯一允许的操作是进行一次比较 comp⁡(i,j)\operatorname{comp}(i, j)，以判断命题 ai≤aja_i \le a_j 的真假。一次比较会产生两种可能的结果，并据此对所有可能的排列进行划分：
  • 若 [ai≤aj]=true[a_i \le a_j] = \text{true}，则在最终排列中必有 pi≤pjp_i \le p_j；
  • 若 [ai≤aj]=false[a_i \le a_j] = \text{false}，则必有 pi>pjp_i > p_j。
也就是说，每一次比较都会将当前仍然可能的排列集合划分为两部分（某一部分也可能为空），而真正的答案排列一定落在其中的一部分中。
我们可以将上述过程抽象为一个 决策树：
  • 决策树的每个节点对应一个排列集合，表示在当前已知比较结果下仍可能成为答案的排列；
  • 根节点对应所有 n!n! 个排列组成的集合；
  • 每进行一次比较，当前节点至多分裂为两个子节点，对应比较结果的两种可能；
  • 无法继续划分等价类即为叶节点，在该节点上，所有仍可能的排列都对应同一个合法输出。
由于不同叶节点对应的排列集合两两无交，而排列总数为 n!n!，因此决策树的叶节点数不超过 n!n!。
决策树是一棵二叉树。对于高度为 hh 的二叉树，其叶节点数至多为 2h2^h，于是有
2h≥n!⟹h≥log⁡2(n!)。2^h \ge n! \quad \Longrightarrow \quad h \ge \log_2(n!)。
因此，任何基于比较的排序算法最坏情况都至少需要 Θ(log⁡2(n!))\Theta(\log_2(n!)) 次比较。
利用 Stirling 公式
n!∼2πn(ne)n,n! \sim \sqrt{2\pi n}\left(\frac{n}{\mathrm e}\right)^n,
可以得到
Θ(log⁡2(n!))=Θ(nlog⁡n−n+log⁡n)=Θ(nlog⁡n)\Theta(\log_2 (n!)) = \Theta(n \log n - n + \log n) = \Theta(n \log n)
综上所述，任何基于比较的排序算法，最坏需要 Θ(nlog⁡n)\Theta(n \log n) 次比较。
另一方面，归并排序、堆排序等经典算法在最坏情况下均能在 O(nlog⁡n)O(n \log n) 次比较内完成排序。因此，这一下界在渐进意义下是紧的。

2. k 路归并

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

问题描述

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

算法

容易想到一个简单的算法，仿照 k=2k = 2 时的双指针做法，每个数组维护一个指针，每次都选择指针中最小的放入答案序列，然后移动指针。这个过程可以通过一个大小为 kk 的堆维护，时间复杂度 O(Nlog⁡k)O(N \log k)。
可能有的同学对这个复杂度不够满意，希望通过更巧妙的方法进一步降低复杂度，那么问题来了：是否存在比 O(Nlog⁡k)O(N \log k) 更快的基于比较的 k 路归并算法呢？
答案是 O(Nlog⁡k)O(N \log k) 已经是最优的时间复杂度了，下面给出证明。

复杂度下界分析

这里可以套用上面的决策树模型，但不同的是我们这次有先验信息：每个数组内部顺序是已知的。
在保持每个数组内部相对顺序不变的前提下，把它们合并成一个序列的方案数，这就是多重集的全排列：
N!n1!n2!⋯nk!\frac{N!}{n_1!n_2!\cdots n_k!}
这就是该决策树的叶子节点数上界，由上例比较排序的分析可得树高 h≥log⁡2(N!n1!n2!⋯nk!)h \ge \log_2 \left(\frac{N!}{n_1!n_2!\cdots n_k!}\right)。
化简得
O(log⁡(Nn1!n2!⋯nk!))=O(Nlog⁡N−∑nilog⁡ni)O\Bigg(\log \left(\frac{N}{n_1!n_2!\cdots n_k!}\right) \Bigg) = O(N \log N - \sum n_i \log n_i)
求上界，则 ∑nilog⁡ni\sum n_i \log n_i 应该取最小值，现在变为求问题：
有 x1+x2+⋯+xk=nx_1 + x_2 + \cdots + x_k = n，已知 f(x)f(x) 为凸函数，求 min⁡f(x1)+⋯+f(xk)\min f(x_1) + \cdots + f(x_k)。
根据琴生不等式，当 x1=x2=⋯=xk=nkx_1 = x_2 = \cdots = x_k = \frac{n}{k} 时，f(x1)+⋯+f(xk)f(x_1) + \cdots + f(x_k) 取最小值。
于是
O(Nlog⁡N−k(Nk)log⁡(Nk))=O(Nlog⁡k)O\Big(N \log N - k \left(\frac{N}{k}\right) \log \left(\frac{N}{k}\right)\Big) = O(N \log k)
综上，k 路归并的时间复杂度下界是 O(Nlog⁡k)O(N \log k)。

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...