Bucket Sort O(n+k) 如果使用插入排序对每个桶进行排序，时间复杂度如何？

Question

由于插入排序的时间复杂度为 O(n^2)，那么桶排序 O(n+k) 在每个桶上使用插入排序时的平均情况时间复杂度如何？这里 k 是桶的数量。

Answer 1

您可以查看平均时间复杂度的详细计算。虽然，这是一个直觉。

首先，在最坏的情况下，桶排序是O(n^2)。每当所有元素都出现在同一个桶中时，就会发生这种情况。

虽然，桶排序依赖于元素在桶中均匀分布。给定这个假设，并且给定与输入大小成比例的桶数，那么平均桶应该包含O(1) 个元素。换句话说，通过选择足够多的桶，你可以保持它们的尺寸很小。

这意味着桶的排序对整体时间复杂度没有影响。选择插入排序成为一个明智的选择，因为它具有较小的开销并且不需要额外的空间。