比较排序 - 理论
有人可以向我解释这个问题的解决方案吗？
假设给定一个由 n 个元素组成的序列进行排序。输入序列 由 n=k 个子序列组成，每个子序列包含 k 个元素。给定中的元素 子序列都小于后续子序列中的元素，并且 大于前一个子序列中的元素。因此，所需要的一切 对长度n的整个序列进行排序就是对每个n=k中的k个元素进行排序 子序列。显示比较次数的 n lg k 下限 需要解决排序问题的这种变体。
解决方案：
设 S 为 n 个元素的序列，分为 n/k 个长度为 k 的子序列 其中任何子序列中的所有元素都大于所有元素 前一个子序列的且小于后继子序列的所有元素 子序列。
声明
任何基于比较的排序算法对 S 进行排序都必须花费 (n lg k) 时间 最坏的情况。
证明
首先注意，正如提示中所指出的，我们无法证明较低的 通过将每个子序列排序的下限相乘来进行限制。 这只能证明没有更快的算法来对子序列进行排序 独立。这不是我们被要求证明的；而是我们被要求证明的。我们无法介绍任何 额外的假设。
现在，考虑 S 的任何比较排序的高度 h 的决策树。 每个子序列的元素可以是任何顺序，任何 k! 排列 对应于子序列的最终排序顺序。并且，由于存在 n/k 个这样的 子序列，每个子序列可以是任意顺序，有(k!)^n/k种排列 S 的值可以对应于某些输入顺序的排序。因此，任何决定 用于排序 S 的树必须至少有 (k!)^n/k 个叶子。由于高度为 h 的二叉树 没有超过 2^h 个叶子，我们必须有 2^h ≥ (k!)^(n/k) 或 h ≥ lg((k !)^n/k)。我们 因此得到
h ≥ lg((k!)^n/k) -- unbalanced parens - final one added?
= (n/k) lg(k!)
≥ (n/k) lg((k/2)^k/2)
= (n/2) lg(k/2)
第三行来自 k!，其 k/2 最大项至少为 k/2。 （我们在这里隐含地假设 k 是偶数。我们可以根据楼层和天花板进行调整 如果k是奇数。）
因为在任何决策树中都存在至少一条路径用于对具有长度的S进行排序 至少(n/2) lg(k/2)，任何基于比较的排序的最坏情况运行时间 S 的算法是(n lg k)。
有人可以引导我完成代码块中的步骤吗？尤其是当 lg k! 变为 lg((k/2)^k/2) 时的步骤。
Can someone explain the solution of this problem to me?
Suppose that you are given a sequence of n elements to sort. The input sequence
consists of n=k subsequences, each containing k elements. The elements in a given
subsequence are all smaller than the elements in the succeeding subsequence and
larger than the elements in the preceding subsequence. Thus, all that is needed to
sort the whole sequence of length n is to sort the k elements in each of the n=k
subsequences. Show an n lg k lower bound on the number of comparisons
needed to solve this variant of the sorting problem.
Solution:
Let S be a sequence of n elements divided into n/k subsequences each of length k
where all of the elements in any subsequence are larger than all of the elements
of a preceding subsequence and smaller than all of the elements of a succeeding
subsequence.
Claim
Any comparison-based sorting algorithm to sort S must take (n lg k) time in the
worst case.
Proof
First notice that, as pointed out in the hint, we cannot prove the lower
bound by multiplying together the lower bounds for sorting each subsequence.
That would only prove that there is no faster algorithm that sorts the subsequences
independently. This was not what we are asked to prove; we cannot introduce any
extra assumptions.
Now, consider the decision tree of height h for any comparison sort for S. Since
the elements of each subsequence can be in any order, any of the k! permutations
correspond to the final sorted order of a subsequence. And, since there are n/k such
subsequences, each of which can be in any order, there are (k!)^n/k permutations
of S that could correspond to the sorting of some input order. Thus, any decision
tree for sorting S must have at least (k!)^n/k leaves. Since a binary tree of height h
has no more than 2^h leaves, we must have 2^h ≥ (k!)^(n/k) or h ≥ lg((k!)^n/k). We
therefore obtain
h ≥ lg((k!)^n/k) -- unbalanced parens - final one added?
= (n/k) lg(k!)
≥ (n/k) lg((k/2)^k/2)
= (n/2) lg(k/2)
The third line comes from k! having its k/2 largest terms being at least k/2 each.
(We implicitly assume here that k is even. We could adjust with floors and ceilings
if k were odd.)
Since there exists at least one path in any decision tree for sorting S that has length
at least (n/2) lg(k/2), the worst-case running time of any comparison-based sorting
algorithm for S is (n lg k).
Can someone walk me through the steps in code block? Especially the step when lg k! becomes lg((k/2)^k/2).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我重新打印了下面的数学：
我们走吧通过这个。从第 (1) 行到第 (2) 行使用对数的属性。类似地，从第 (3) 行到第 (4) 行使用对数的属性和 (n / k)(k / 2) = (n / 2) 的事实。所以技巧步骤是从第 (2) 行到第 (3) 行。
这里的主张如下：
直观上，想法如下。考虑k! = k(k - 1)(k - 2)...(2)(1)。如果您会注意到，这些项中有一半大于 k / 2，一半则小于 k / 2。如果我们删除所有小于 k 的项，我们会得到（接近）以下内容：
现在，我们有 k / 2 ≥ k，所以我们有
这是 (k / 2) 与本身 (k / 2) 次，因此等于 (k / 2)k/2。这个数学并不精确，因为奇数和偶数的逻辑有点不同，但本质上使用这个想法，你可以得到早期结果的证明草图。
总结一下：（1）到（2）和（3）到（4）使用了对数的性质，而（2）到（3）使用了上面的结果。
希望这有帮助！
I've reprinted the math below:
Let's walk through this. Going from line (1) to line (2) uses properties of logarithms. Similarly, going from line (3) to line (4) uses properties of logarithms and the facththat (n / k)(k / 2) = (n / 2). So the trick step is going from line (2) to line (3).
The claim here is the following:
Intuitively, the idea is as follows. Consider k! = k(k - 1)(k - 2)...(2)(1). If you'll notice, half of these terms are greater than k / 2 and half of them are smaller. If we drop all the terms that are less than k, we get something (close to) the following:
Now, we have that k / 2 ≥ k, so we have that
This is the product of (k / 2) with itself (k / 2) times, so it's equal to (k / 2)k/2. This math isn't precise because the logic for odd and even values are a bit different, but using essentially this idea you get a sketch of the proof of the earlier result.
To summarize: from (1) to (2) and from (3) to (4) uses properties of logarithms, and from (2) to (3) uses the above result.
Hope this helps!