桶排序何时具有线性时间复杂度？基于n和k的“足够均匀”判定条件

桶排序的线性时间复杂度依赖于元素在桶中的分布特性，所谓“足够均匀”，核心是元素在各个桶中的分布没有显著倾斜——不存在某个桶容纳了绝大多数元素，或者少数桶的元素数量远高于平均水平的情况。

用元素数n和桶数k量化“足够均匀” #

桶排序的总时间复杂度可拆解为：分桶的O(n) + 每个桶内部排序的时间总和 + 合并桶的O(n)。其中桶内排序通常用插入排序，单桶时间为O(mᵢ²)（mᵢ是第i个桶的元素数），因此总时间为 O(n + Σ(mᵢ²))。要让总时间达到线性O(n)，关键是让Σ(mᵢ²) = O(n)。

基于这个核心，我们可以通过n和k定义“足够均匀”的条件：

• 首先，桶的数量k需要与元素数量n同量级，即k = Θ(n)（比如取k=n，或k=⌈n/c⌉，c为某个固定常数）。
• 在k=Θ(n)的前提下，要求每个桶的元素数量mᵢ的最大值为常数级，或者说每个mᵢ与平均水平n/k的偏差被严格控制。此时每个mᵢ≈O(1)，Σ(mᵢ²)=k*O(1)=O(n)，恰好满足总时间线性的要求。

换个直观表述：如果把n个元素分到k个桶里，当没有任何一个桶的元素数超过某个固定常数C，且k和n同阶时，就可以认为分布“足够均匀”。

举个反例：如果有一个桶里装了O(n)个元素，那么Σ(mᵢ²)会达到O(n²)，总时间直接退化为O(n²)，这就是典型的分布不够均匀的情况。而严格均匀分布下，每个桶的元素数要么是⌊n/k⌋要么是⌈n/k⌉，当k=n时，每个桶最多1个元素，Σ(mᵢ²)=n，完全满足线性时间的条件。

内容的提问来源于stack exchange，提问作者thefool