一小部分输入的比较排序下限？
有人可以引导我完成以下问题解决方案的数学部分吗？
证明不存在运行时间至少一半是线性的比较排序 的 n!长度为 n 的输入。长度为 n 的输入的 1/n 的分数怎么样？ 那么分数 (1/(2)^n) 呢？
解决方案：
如果排序在线性时间内运行 m 个输入排列，则高度 h 决策树的一部分，由 m 个相应的叶子及其 祖先是线性的。 使用与定理 8.1 的证明相同的论证来证明这是不可能的 对于 m = n!/2、n!/n 或 n!/2n。 我们有 2^h ≥ m，这使得我们 h ≥ lGM。对于此处给出的所有可能的毫秒数， LGm = Ω(n lg n)，因此 h = Ω(n lg n)。 尤其，
lgn!/2= lg n! − 1 ≥ n lg n − n lg e − 1
lgn!/n= lg n! − lg n ≥ n lg n − n lg e − lg n
lgn!/2^n= lg n! − n ≥ n lg n − n lg e − n
Can someone please walk me through mathematical part of the solution of the following problem.
Show that there is no comparison sort whose running time is linear for at least half
of the n! inputs of length n. What about a fraction of 1/n of the inputs of length n?
What about a fraction (1/(2)^n)?
Solution:
If the sort runs in linear time for m input permutations, then the height h of the
portion of the decision tree consisting of the m corresponding leaves and their
ancestors is linear.
Use the same argument as in the proof of Theorem 8.1 to show that this is impossible
for m = n!/2, n!/n, or n!/2n.
We have 2^h ≥ m, which gives us h ≥ lgm. For all the possible ms given here,
lgm = Ω(n lg n), hence h = Ω(n lg n).
In particular,
lgn!/2= lg n! − 1 ≥ n lg n − n lg e − 1
lgn!/n= lg n! − lg n ≥ n lg n − n lg e − lg n
lgn!/2^n= lg n! − n ≥ n lg n − n lg e − n
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这些证明中的每一个都是对更一般证明的直接修改，即您不能有比 Ω(n log n) 排序更快的比较排序（您可以看到这个证明 在此之前的答案中）。直观上，论证如下。为了使排序算法正常工作，它必须能够确定元素的初始顺序。否则，它无法对值重新排序以将它们按升序排列。给定 n 个元素，有 n!这些元素的不同排列，意味着有 n！排序算法的不同输入。
最初，算法对输入序列一无所知，并且无法区分 n!不同的排列。每次算法进行比较时，它都会获得更多有关元素排序方式的信息。具体来说，它可以判断输入排列是在比较结果为真的排列组中还是在比较结果为假的排列组中。您可以将算法作为二叉树进行可视化，其中每个节点对应于算法的某些状态，并且特定节点的（最多）两个子节点指示如果比较结果为 true 则将进入的算法状态或假。
为了使排序算法能够正确排序，它必须能够为每个可能的输入输入唯一的状态，否则算法将无法区分两个不同的输入序列，因此将至少对其中一个进行排序错误地。这意味着，如果考虑树中叶节点的数量（算法已完成比较并将进行排序的部分），则每个输入排列必须至少有一个叶节点。一般证明中，有n!排列，所以必须至少有 n!叶节点。在二叉树中，拥有 k 个叶节点的唯一方法是高度至少为 Ω(log k)，这意味着您必须至少进行 Ω(log k) 比较。因此，根据斯特林近似，一般排序下界为 Ω(log n!) = Ω(n log n)。
在您正在考虑的情况下，我们将自己限制为这些可能排列的子集。例如，假设我们希望能够对 n! 进行排序。 / 2 的排列。这意味着我们的树的高度必须至少为 lg (n!/ 2) = lg n! - 1 = Ω(n log n)。因此。你不能在 O(n) 时间内排序，因为没有线性函数以 Ω(n log n) 的速率增长。第二部分，看看你能不能得到n! / n 以线性时间排序，同样，决策树的高度必须为 lg (n!/ n) = lg n! - lg n = Ω(n log n)，因此无法在 O(n) 比较中进行排序。对于最后一个，我们有 lg n! / 2n = lg n！ - n = Ω(n log n) 也是如此，所以同样不能在 O(n) 时间内排序。
但是，您可以在线性时间内对 2n 个排列进行排序，因为 lg 2n = n = O(n)。
希望这有帮助！
Each of these proofs are a straightforward modification of the more general proof that you can't have a comparison sort that sorts any faster than Ω(n log n) (you can see this proof in this earlier answer). Intuitively, the argument goes as follows. In order for a sorting algorithm to work correctly, it has to be able to determine what the initial ordering of the elements is. Otherwise, it can't reorder the values to put them in ascending order. Given n elements, there are n! different permutations of those elements, meaning that there are n! different inputs to the sorting algorithm.
Initially, the algorithm knows nothing about the input sequence, and it can't distinguish between any of the n! different permutations. Every time the algorithm makes a comparison, it gains a bit more information about how the elements are ordered. Specifically, it can tell whether the input permutation is in the group of permutations where the comparison yields true or in the group of permutations where the comparison yields false. You can visualize how the algorithm works as a binary tree, where each node corresponds to some state of the algorithm, and the (up to) two children of a particular node indicate the states of the algorithm that would be entered if the comparison yields true or false.
In order for the sorting algorithm to be able to sort correctly, it has to be able to enter a unique state for each possible input, since otherwise the algorithm couldn't distinguish between two different input sequences and would therefore sort at least one of them incorrectly. This means that if you consider the number of leaf nodes in the tree (parts where the algorithm has finished comparing and is going to sort), there must be at least one leaf node per input permutation. In the general proof, there are n! permutations, so there must be at least n! leaf nodes. In a binary tree, the only way to have k leaf nodes is to have height at least Ω(log k), meaning that you have to do at least Ω(log k) comparisons. Thus the general sorting lower bound is Ω(log n!) = Ω(n log n) by Stirling's approximation.
In the cases that you're considering, we're restricting ourselves to a subset of those possible permutations. For example, suppose that we want to be able to sort n! / 2 of the permutations. This means that our tree must have height at least lg (n! / 2) = lg n! - 1 = Ω(n log n). As a result. you can't sort in time O(n), because no linear function grows at the rate Ω(n log n). For the second part, seeing if you can get n! / n sorted in linear time, again the decision tree would have to have height lg (n! / n) = lg n! - lg n = Ω(n log n), so you can't sort in O(n) comparisons. For the final one, we have that lg n! / 2n = lg n! - n = Ω(n log n) as well, so again it can't be sorted in O(n) time.
However, you can sort 2n permutations in linear time, since lg 2n = n = O(n).
Hope this helps!