28

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

它使用 a 背后的原理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)，即使它以一种时髦的格式返回结果？

4

2 回答 2

152

直接回答你的问题：

  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) 个不同的状态。如果是这种情况，那么数组中的元素必须有两种不同的排序，算法总是将它们组合在一起进入相同的状态。如果发生这种情况，那么排序算法不可能正确地对两个输入数组进行正确排序。这背后的原因是，由于算法对两个数组的处理方式相同，因此它用于对第一个数组的元素进行重新排序的任何步骤都将与它用于对第二个数组的元素进行重新排序的步骤相同。由于这两个数组不相同，因此在这两种情况之一中必须至少有一个元素不合适。最后，

但是算法如何进入这些不同的状态呢？好吧，让我们考虑一下。最初，该算法根本没有关于元素排序的信息。当它进行第一次比较时（例如，在元素 A[i] 和 A[j] 之间），算法可以进入两种状态之一——一种是 A[i] < A[j]，另一种是 A[i] > 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! 不同的零数组和长度为 n 的数组。事实上，它们只有 2 n个。根据我们上面的结果，这意味着我们应该能够使用纯粹基于比较的排序算法在 Ω(log 2 n ) = Ω(n) 时间内进行排序。事实上，我们绝对可以做到这一点；这是我们如何做的草图：

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

看看这是否有效，如果 0 是我们的第一个元素，那么“less”数组将为空，“equal”数组将包含所有零，而“greater”数组将包含所有 1。连接它们然后将所有的零放在所有的前面。否则，如果 1 是我们的第一个元素，则less数组将保存 0，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) 排序障碍。

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

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

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

希望这可以帮助！

于 2011-08-23T01:35:20.493 回答
8

这被称为Radix Sort，是的，它打破了 nlog(n) 障碍，这只是Comparison Model. 在链接到比较模型的维基百科页面上，您可以看到使用它的分类列表，以及一些不使用的列表。

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

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

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

于 2011-08-23T01:23:20.840 回答