algorithm - 使用堆排序可以排序的元素数量？

Question

我在考试中遇到了一个非常困惑的问题，并尝试了错误，这是一个客观型问题，给出了四个选项，现在我知道正确的选项，但我没有解释。

问题:

使用堆排序在Ɵ(logn)时间内可以排序的元素数量为

a)Ɵ(1)

b) Ɵ(√ log n)

c) Ɵ(log n/loglog n)

d) Ɵ(log n)

选项c正确。

我选择了选项a)，我认为在log n时间内只有一个元素会被排序，这是错误的，我不知道为什么选项c)是正确的。

Answer 1

忽略这个问题要求堆排序上的 Theta 绑定(bind)这一事实，而在一般情况下它没有，这就是为什么这令人困惑:

在处理 Landau 表示法(= O、Ɵ、Omega 之类的东西)时，我们习惯将输入大小指定为 n ;这里问你的是“我们必须将输入大小设置为多少才能获得 Ɵ(log n) 的复杂度”。

例如:考虑列表遍历；这将带你O(n)对于尺寸列表 n 。另一方面，如果我们将输入限制为 log n对于一些n ，我们得到的复杂度为O(log n) 。将这个想法转移到排序算法中，我们知道堆排序的最坏情况复杂度为 O(n log n)如果我们给它一个大小为 n 的列表。那么如果我们给它一个大小为 log n 的列表，会发生什么？ ？复杂性变得更少:我们从(n) log (n)开始至

(log n) log (log n) = log n log log n

现在为了解释为什么 c) 是正确答案，我会写 l(n)而不是log n使其更具可读性。

调整项 n * l(n) 中的输入大小至l(n)/l(l(n))这就是 c) 所说的。然后我们得到:

l(n)/l(l(n)) * l(l(n)/l(l(n)))
= l(n)/l(l(n)) * [l(l(n) - l(l(l(n)))]
= l(n) - [l(n) * l(l(l(n)))]/l(l(n))

正如您所看到的(希望)，主导术语是 l(n) = log n ，因此对于大小为 l(n)/l(l(n)) 的输入，堆排序的最坏情况复杂度为 O(log n) 。然而，Theta 对于一般情况来说肯定是错误的。

旁注:有人知道如何使条款变得漂亮吗？我知道我们这里没有内联 LaTeX，但这看起来一点也不好看。