由于插入排序的时间复杂度是 O(n^2),桶排序的平均时间复杂度是 O(n+k),因为它在每个桶上使用插入排序? 这里 k 是桶的数量。
最佳答案
你可以看看detailed calculations的平均时间复杂度。虽然,这是一种直觉。
首先,在最坏的情况下,桶排序是 O(n^2)。只要所有元素都在同一个桶中,就会发生这种情况。
尽管如此,桶排序依赖于元素在桶中均匀分布。鉴于该假设,并给定与输入大小成比例的桶数,则平均桶应包含 O(1) 个元素。换句话说,通过选择足够多的桶,您可以保持它们的尺寸较小。
这意味着桶的排序对整体时间复杂度没有影响。选择插入排序就成为一个明智的选择,因为它的开销更小并且不需要额外的空间。
关于algorithm - 如果使用插入排序对每个桶进行排序,桶排序O(n+k)的时间复杂度如何?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54808131/