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

Question

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

问题:

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

一)Ɵ(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) 的复杂度”。

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