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

Question

由于插入排序的时间复杂度是O(n^2)，那么桶排序O(n+k)在每个桶上使用插入排序时的平均案例时间复杂度是怎样的？这里k是桶的数目。

Answer 1

您可以查看平均时间复杂度的详细计算。不过，这里有一个直觉。

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

尽管如此，桶排序依赖于在桶中统一分布的元素。考虑到这个假设，并给出与输入大小成比例的桶数，那么平均桶应该包含O(1)元素。换句话说，通过选择足够多的水桶，你可以使它们的大小保持较小。

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