1

有人可以向我解释这个问题的解决方案吗？

假设给定一个包含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 个这样的子序列，每个子序列都可以按任何顺序排列，因此 S 的(k!)^n/k个排列可能对应于某些输入顺序的排序。因此，任何对 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是奇数，我们可以调整地板和天花板。）

由于在任何决策树中至少存在一条对长度至少为(n/2) lg(k/2)的 S 进行排序的路径，因此任何基于比较的 S 排序算法的最坏情况运行时间为(n lg ķ）。

有人可以指导我完成代码块中的步骤吗？尤其是lg k! 变为lg((k/2)^k/2)。

4

1 回答 1

4

我重印了下面的数学：

(1) h≥lg(k! n/k )

(2) = (n/k) lg(k!)

(3) ≥ (n/k) lg((k/2) k/2 )

(4) = (n/2) lg(k/2)

让我们来看看这个。从第 (1) 行到第 (2) 行使用对数的性质。类似地，从第 (3) 行到第 (4) 行使用对数的性质和 (n / k)(k / 2) = (n / 2) 的事实。所以技巧步骤是从第 (2) 行到第 (3) 行。

这里的主张如下：

对于所有 k，k！≥ (k / 2) (k / 2)

直观地说，思路如下。考虑k！= k(k - 1)(k - 2)...(2)(1)。如果您会注意到，这些术语中有一半大于 k / 2，而其中一半小于。如果我们删除所有小于 k 的项，我们会得到（接近）以下内容：

！≥ k(k - 1)(k - 2)...(k / 2)

现在，我们有 k / 2 ≥ k，所以我们有

！≥ k(k - 1)(k - 2)...(k / 2) ≥ (k/2)(k/2)...(k/2)

这是 (k / 2) 与自身 (k / 2) 次的乘积，因此它等于 (k / 2) k/2。这个数学并不精确，因为奇数和偶数的逻辑有点不同，但基本上使用这个想法，你会得到早期结果证明的草图。

总结一下：从（1）到（2）和从（3）到（4）使用对数的性质，从（2）到（3）使用上述结果。

希望这可以帮助！

于 2012-02-16T00:43:40.000 回答