比较排序 - 理论

Question

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

假设您有一个序列 n 要排序的元素。输入序列包括 n = k 子序列，每个都包含 k 元素。给定子序列中的元素都小于成功子序列中的元素，并且比上一个子序列中的元素大。因此，要对整个长度进行分类所需的一切 n 是为了排序 k 每个元素 n = k子序列。显示一个 n lg k 在解决分类问题的这种变体所需的比较数量上的下限。

解决方案：

让 s sequ n 元素分为 N/K。 子序列长度 k如果任何子序列中的所有元素都大于前一个子序列的所有元素，并且小于后续分子的所有元素。

宣称

任何基于比较的分类算法 s 一定要拿 （n lg k） 在最坏的情况下。

证明

首先注意到，正如提示中指出的那样，我们无法通过将下限乘以分类每个子序列来证明下限。这只会证明没有更快的算法可以独立地对子序列进行分类。这不是我们被要求证明的。我们不能介绍任何额外的假设。

现在，考虑对S的高度h的决策树。用于S的任何比较排序。因为每个子序列的元素可以按任何顺序，任何一个 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 很奇怪。）

由于在任何决策树中至少存在至少具有长度的决策树中的一条路径 （N/2）LG（K/2）, ，任何基于比较的分类算法的最糟糕的运行时间是 （n lg k）.

有人可以在代码块中引导我浏览步骤吗？特别是何时 lg k！ 变成 LG（（K/2）^K/2）.

Answer 1

我已经重印了以下数学：

（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）使用对数的属性和Facththat（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（k -1）（k -2）...（k / 2）

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

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）使用上述结果。

希望这可以帮助！