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

Question

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

Answer 1

你可以看看detailed calculations的平均时间复杂度。虽然，这是一种直觉。

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

尽管如此，桶排序依赖于元素在桶中均匀分布。鉴于该假设，并给定与输入大小成比例的桶数，则平均桶应包含 O(1) 个元素。换句话说，通过选择足够多的桶，您可以保持它们的尺寸较小。

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