我在考试中遇到了一个非常混乱的问题并且尝试错了，这是一个客观类型的问题，给出了四个选项，现在我知道正确的选项但我没有解释。
问题 ：
使用 heapsort 在Ɵ(logn) 时间内可以排序的元素数是
a) Ɵ(1)
b)Ɵ(√log n)
c)Ɵ(log n / loglog n)
d)Ɵ(log n)
选项c是正确的。
我选择了选项 a)，我认为在 log n 时间内只有一个元素会被排序，这是错误的，我不知道为什么选项 c) 是正确的。
问问题
1405 次
2 回答
2
忽略这个问题要求在堆排序上绑定 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 内联，但这看起来一点也不好看。
于 2013-04-03T20:30:14.070 回答
0
令 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) 的转换主要是基于“直觉”。我有理由相信它是正确的或至少“几乎正确”，但我不知道我用来证明这一点的正式规则。
于 2013-04-03T20:29:50.053 回答