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

Question

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

问题 ：

使用 heapsort 在Ɵ(logn) 时间内可以排序的元素数是

a) Ɵ(1)

b)Ɵ(√log n)

c)Ɵ(​​log n / loglog n)

d)Ɵ(log n)

选项c是正确的。

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

Answer 1

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

在处理朗道表示法（= O，Ɵ，Omega 的东西）时，我们习惯于将输入大小指定为n; 您在这里被问到的是“我们必须将输入大小设置为什么才能获得Ɵ（log n）的复杂性”。

例如：考虑列表遍历；这将带您O(n)查看大小列表n。另一方面，如果我们将输入限制log n为 一些n，我们会得到 的复杂度O(log n)。将这个想法转移到排序算法中，我们知道O(n log n)如果我们给它一个 size 的列表，堆排序的最坏情况复杂度n。那么如果我们给它一个 size 列表会发生什么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 内联，但这看起来一点也不好看。

Answer 2

令 t=exp(n) 为您拥有的时间，m 为您在该时间内可以排序的项目数。

a) m = Θ(1) ⇒ t → ∞：无论何时，您都只能对有限数量的项目进行排序。
b) m = Θ(√t) ⇒ t = Θ(m²)：你需要二次时间。愚蠢的冒泡排序。
c) m = Θ(t/log t) ⇒ t = Θ(m log m)：这是堆排序的复杂度。
d) m = Θ(t) ⇒ t = Θ(m)：线性时间排序好得令人难以置信。

我必须承认 c) 的转换主要是基于“直觉”。我有理由相信它是正确的或至少“几乎正确”，但我不知道我用来证明这一点的正式规则。