<分区>
使用堆排序可以在 Θ(log n) 时间内对多少个元素进行排序？
当我们进行堆排序时，要构建堆，我们需要 Θ(n) 复杂度，然后进行堆排序 O(nlog n)。我理解这个概念。但是当涉及到我们这里的问题时，我们甚至无法在 Θ(log n) 时间内构建一个 n 个元素的堆。那么考虑输入大小 n 的答案是 O(1) 吗？
我还看到了一种不同的解释，它根据输入大小 logn 得出复杂度为 Θ(log n/log log n)。我也不太遵循这种方法。那么哪个是正确答案，为什么？
<分区>
使用堆排序可以在 Θ(log n) 时间内对多少个元素进行排序？
当我们进行堆排序时，要构建堆，我们需要 Θ(n) 复杂度，然后进行堆排序 O(nlog n)。我理解这个概念。但是当涉及到我们这里的问题时，我们甚至无法在 Θ(log n) 时间内构建一个 n 个元素的堆。那么考虑输入大小 n 的答案是 O(1) 吗？
我还看到了一种不同的解释，它根据输入大小 logn 得出复杂度为 Θ(log n/log log n)。我也不太遵循这种方法。那么哪个是正确答案，为什么？
最佳答案
我认为问题是“假设某处有一个已知的 n 值，作为 n 的函数，数组大小的渐近边界是多少，其中使用堆排序对该数组进行排序将花费时间 Θ(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))
请注意，随着 n 趋于无穷大，1 - log log log n/log log n 趋于 1，因此根据需要，上述表达式实际上是 Θ(log n)。
因此，如果您尝试使用堆排序对大小为 Θ(log n/log log n) 的数组进行排序，作为 n 的函数，运行时间为 Θ(log n)。
希望这对您有所帮助!
关于algorithm - 使用堆排序可以在 Θ(log n) 时间内对多少个元素进行排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21156015/