“(n log n) 屏障”的规则是什么？用于排序算法？

Question

我写了一个简单的程序，排序时间复杂度为 O(n)。它的内存效率非常低，但这不是重点。

它使用 HashMap 背后的原理进行排序：

public class NLogNBreak {
    public static class LinkedListBack {
        public LinkedListBack(int val){
            first = new Node();
            first.val = val;
        }
        public Node first = null;
        public void insert(int i){
            Node n = new Node();
            n.val = i;
            n.next = first;
            first = n;
        }
    }

    private static class Node {
        public Node next = null;
        public int val;
    }

    //max > in[i] > 0
    public static LinkedListBack[] sorted(int[] in, int max){
        LinkedListBack[] ar = new LinkedListBack[max + 1];
        for (int i = 0; i < in.length; i++) {
            int val = in[i];
            if(ar[val] == null){
                ar[val] = new LinkedListBack(val);
            } else {
                ar[val].insert(val);
            }
        }
        return ar;
    }
}

那么，即使它以一种时髦的格式返回结果，这也算作一种 O(n) 吗？

Answer 1

直接回答你的问题：

1. 从技术上讲，你的排序算法不是 O(n) 而是 O(n + max)，因为你需要创建一个大小为 max 的数组，这需要 O(max) 时间。
2. 这不是问题；事实上，这是打破 Ω(n log n) 障碍的著名排序算法的特例。

那么这个 Ω(n log n) 势垒是什么？它从哪里来？你如何打破它？

Ω(n log n) 屏障

Ω(n log n) 屏障是任何基于比较的排序算法的平均情况速度的信息理论下限。如果允许您应用于数组元素以区分它们的唯一操作是执行某种比较，那么您的排序算法在平均情况下不会比 Ω(n log n) 更好。

为了理解其中的原因，让我们考虑一下算法在执行过程中任意时刻的状态。当算法运行时，它可以获得一些有关输入元素排序方式的信息。假设，如果算法有一些关于输入元素原始排序的信息 X，那么算法就处于状态 X。

Ω(n log n) 参数（以及几个相关参数，我将在稍后讨论）的问题是算法必须能够根据输入进入大量不同的状态。现在我们假设排序算法的输入是一个包含 n 个不同值的数组。因为除了这些元素的排序方式之外，算法无法告诉任何有关这些元素的信息，因此排序的值是什么并不重要。重要的是这 n 个元素之间的相对顺序。

现在是关键步骤 - 假设有 f(n) 种独特的方式对 n 个输入元素进行排序，并假设我们的排序算法不能进入至少 f(n) 种不同的状态。如果是这种情况，那么数组中的元素必须有两种不同的顺序，算法总是将它们组合在一起形成相同的状态。如果发生这种情况，则排序算法不可能对两个输入数组进行正确排序。其背后的原因是，由于该算法对两个数组的处理方式相同，因此无论它使用什么步骤对第一个数组的元素重新排序，都将与它对第二个数组的元素重新排序所使用的步骤相同。由于这两个数组不相同，因此在这两种情况之一中必须至少有一个元素不合适。因此，我们知道排序算法必须能够进入 f(n) 个不同的状态。

但算法如何进入这些不同的状态呢？好吧，让我们考虑一下。最初，该算法根本没有有关元素排序的信息。当它进行第一次比较时（例如，在元素 A[i] 和 A[j] 之间），算法可以进入两种状态之一 - 其中一种状态是 A[i] < 。 A[j]和其中A[i]＞1的一个。 A[j]。更一般地，在最好的情况下，算法进行的每次比较都可以根据比较结果将算法置于两个新状态之一。因此，我们可以想到一个大型二叉树结构，描述算法可以处于的状态 - 每个状态最多有两个子状态，根据比较的结果描述算法进入的状态。如果我们采用从树根到叶子的任何路径，我们就会得到一系列比较，最终由算法对特定输入进行比较。为了尽可能快地排序，我们希望进行尽可能少的比较，因此我们希望这个树结构具有尽可能小的高度。

现在，我们知道两件事。首先，我们可以将算法可以进入的所有状态视为二叉树。其次，该二叉树中必须至少有 f(n) 个不同的节点。鉴于此，我们可以构建的最小可能的二叉树的高度必须至少为 Ω(log f(n))。这意味着，如果有 f(n) 种可能的不同方式对数组元素进行排序，我们必须平均进行至少 Ω(log f(n)) 次比较，否则我们无法进入足够多的不同状态。

为了证明你无法打败 Ω(n log n)，请注意，如果数组中有 n 个不同的元素，那么就有 n！对元素进行排序的不同可能方式。使用斯特林近似，我们得到了log n！ = Ω(n log n)，因此在平均情况下我们必须至少进行 Ω(n log n) 次比较才能对输入序列进行排序。

规则的例外

在上面我们刚刚看到的内容中，我们看到如果有 n 个全部不同的数组元素，则使用比较排序对它们进行排序的速度不能比 Ω(n log n) 更快。然而，这个最初的假设并不一定有效。我们想要排序的许多数组中可能包含重复的元素。例如，假设我想要对仅由 0 和 1 组成的数组进行排序，例如这里的这个数组：

 0 1 0 1 1 1 0 0 1 1 1

在这种情况下，有 n 个是不。不同的 0 和 1 长度为 n 的数组。事实上，只有 2ⁿ 个。从上面的结果来看，这意味着我们应该能够使用纯粹基于比较的排序算法在 Ω(log 2ⁿ) = Ω(n) 时间内进行排序。事实上，我们完全可以做到这一点；下面是我们如何做到这一点的一个草图：

1. 看看第一个元素。
2. 将小于第一个元素的所有元素复制到名为“less”的数组中
3. 将等于第一个元素的所有元素复制到名为“equal”的数组中
4. 将大于第一个元素的所有元素复制到名为“greater”的数组中
5. 连接所有三个元素数组按照小于、等于、大于的顺序排列在一起。

要看到它是否有效，如果 0 是我们的第一个元素，那么“less”数组将为空，“equal”数组将包含所有零，“greater”数组将包含所有 1。将它们连接起来，然后将所有的零放在所有的前面。否则，如果 1 是我们的第一个元素，则 less 数组将保存零，equal 数组将保存 1，而 greater数组将为空。因此，根据需要，它们的串联是全零后跟全一。

在实践中，您不会使用此算法（您将使用计数排序，如下所述），但它表明您确实可以使用基于比较的算法击败 Ω(n log n) 如果可能的输入数量对算法的影响很小。

众所周知，一些基于比较的排序算法可以非常快速地处理具有多个重复值的输入。例如，众所周知，具有特殊分区步骤的快速排序可以利用输入数组中的重复元素。

非比较排序

所有这些讨论都假设我们正在讨论基于比较的排序，其中对数组元素唯一允许的操作是比较。但是，如果我们更多地了解要排序的元素，并且可以对这些元素执行除简单比较之外的操作，那么上述界限都不再成立。我们打破了最初的假设，这些假设导致我们构建了算法所有状态的二叉树，因此没有理由怀疑这些界限仍然成立。

例如，如果您知道输入值是从仅具有 |U| 的 Universe 中提取的其中的元素，然后您可以使用巧妙的算法在 O(n + |U|) 时间内排序。首先创建 |U|我们可以将原始数组中的元素放入不同的桶中。然后，迭代数组并将所有数组元素分配到相应的存储桶中。最后，访问每个存储桶，从保存最小元素副本的存储桶开始，到包含最大元素副本的存储桶结束，然后将找到的所有值连接在一起。例如，让我们看看如何对由值 1 - 5 组成的数组进行排序。如果我们有这个起始数组：

1 3 4 5 2 3 2 1 4 3 5

那么我们可以将这些元素放入桶中，如下所示：

Bucket     1  2  3  4  5
           -------------
           1  2  3  4  5
           1  2  3  4  5
                 3

迭代桶并将它们的值连接在一起会产生以下结果

1 1 2 2 3 3 3 4 4 5 5

：足够了，是我们原始数组的排序版本！这里的运行时间是 O(n) 时间将原始数组元素分配到存储桶中，然后是 O(n + |U|) 时间迭代所有存储桶将元素重新组合在一起。请注意，如果 |U| = O(n)，这在 O(n) 时间内运行，打破了 Ω(n log n) 排序障碍。

如果您要对整数进行排序，则可以使用 基数排序 做得更好，它运行时间复杂度为 O(n lg |U|)。如果您正在处理原始 int，则 lg |U|通常是 32 或 64，所以速度非常快。如果您愿意实现一个特别棘手的数据结构，您可以使用 van Emde Boas 树 在 O(n lg lg U) 时间内对整数从 0 到 U - 1 进行排序，再次利用整数由可以在块中操作的位组组成的事实。

同样，如果您知道元素是字符串，则可以通过构建 trie 来快速排序从字符串中取出，然后迭代特里树以重建所有字符串。或者，您可以将字符串视为以大基数（例如 ASCII 文本的基数 128）编写的数字，然后使用上面的整数排序算法之一。

在每种情况下，您能够克服信息论障碍的原因是您打破了障碍的起始假设，即您只能应用比较。如果您可以将输入元素视为数字、字符串或任何其他能够揭示更多结构的元素，那么所有的赌注都会被取消，您可以非常有效地进行排序。

Answer 2

这就是所谓的 基数排序，是的，它打破了 nlog(n) 障碍，即只是比较模型上的一个障碍。在比较模型链接的维基百科页面上，您可以看到使用它的种类列表，以及一些不使用它的种类的列表。

基数排序通过将每个元素根据其值放入一个存储桶中进行排序，然后在最后将所有存储桶再次连接在一起。它仅适用于具有有限数量可能值的整数等类型。

通常，基数排序一次一个字节或半字节进行，以减少存储桶的数量。请参阅有关它的维基百科文章，或搜索更多信息。

您还可以对负数进行排序，并且只为它用来改进负数的存储桶分配内存。