使用堆排序可以在Θ(log n)时间内对多少个元素进行排序？

Question

使用堆排序可以在Θ(log n)时间内对多少个元素进行排序？

当我们进行堆操作时,为了构建堆,我们需要Θ(n)复杂度,然后执行heapsort O(nlog n).我理解这个概念.但是当谈到我们的问题时,我们甚至无法在Θ(log n)时间内构建一堆n个元素.答案是O(1)考虑输入大小n？

我还看到了一个不同的解释,它将复杂度推导为考虑输入大小logn的Θ(log n/log log n).我也不太关注这种方法.那么哪个是正确的答案？为什么？

Answer 1

我认为问题是"假设某个地方有一个已知值n,数组大小的渐近界限是什么,作为n的函数,用heapsort对数组进行排序需要时间Θ(log n)？ "

当k增长时,用k个元素对数组进行排序需要时间Θ(k log k).您希望选择k使得Θ(k log k)=Θ(log n).选择k =Θ(log n)不一定有效,因为Θ(k log k)=Θ(log n log log n)≠θ(log n).另一方面,如果选择k =Θ(log n/log log n),那么排序的运行时间将是

Θ((log n/log log n)log(log n/log log n))

=Θ((log n/log log n)(log log n - log log log n))

=Θ(log n - log n log log log n/log log n)

=Θ(log n(1 - log log log n/log log n))

请注意,1 - log log log n/log log n趋向于1,因为n变为无穷大,因此上述表达式实际上是Θ(log n),根据需要.

因此,如果您尝试使用堆排序对大小为Θ(log n/log log n)的数组进行排序,则作为n的函数,运行时为Θ(log n).

希望这可以帮助!