performance - “Ω(n log n) barrier”用于排序算法的规则是什么？

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

要直接回答您的问题:

从技术上说，您的排序算法不是O(n)，而是O(n + max)，因为您需要创建一个大小为max的数组，这需要O(max)时间。

这不是问题；实际上，这是一种著名的排序算法的特例，它打破了Ω(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]。更一般而言，在最佳情况下，算法进行的每个比较都可以根据比较结果将算法置于两个新状态之一。因此，我们可以想到一个描述该算法可能处于的状态的大型二叉树结构-每个状态最多具有两个子对象，这些子对象根据进行的比较结果描述该算法进入的状态。如果我们采用从树的根部到叶的任何路径，则会得到一系列比较，最终由算法在特定输入上进行。为了尽可能快地进行排序，我们希望使比较的次数最少，因此我们希望此树结构的高度尽可能小。

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

要总结证明您无法击败Ω(n log n)的证明，请注意，如果数组中包含n个不同的元素，那么就有n个!元素排序的不同可能方式。使用 Stirling's approximation ，我们得到了该日志n! =Ω(n log n)，因此我们必须在平均情况下至少进行Ω(n log n)比较才能对输入序列进行排序。

规则异常(exception)

在上面看到的内容中，我们看到，如果您拥有n个完全不同的数组元素，则无法使用比较排序对它们进行排序，其速度比Ω(n log n)快。但是，此初始假设不一定有效。我们想要排序的许多数组中可能包含重复的元素。例如，假设我要对仅由零和一组成的数组进行排序，例如此处的数组:

 0 1 0 1 1 1 0 0 1 1 1

在这种情况下，不存在n!零的不同数组和长度为n的数组。实际上，它们只有2n。根据上面的结果，这意味着我们应该能够使用纯基于比较的排序算法以Ω(log 2n)=Ω(n)的时间进行排序。实际上，我们绝对可以做到；这是我们如何做的草图:

查看第一个元素。

将少于第一个元素的所有元素复制到名为“less”的数组

将等于第一个元素的所有元素复制到称为“等于”的数组

将大于第一个元素的所有元素复制到名为“greater”的数组

将这三个数组的所有顺序按少，相等，大的顺序连接在一起。

要知道这是可行的，如果第一个元素为0，则'less'数组将为空，'equal'数组将具有全零，而'greater'数组将具有全零。然后将它们串联起来，将所有零放在所有零之前。否则，如果1是我们的第一个元素，则 less数组将保留零， equal数组将保留零，并且 greater数组将为空。因此，根据需要，它们的连接是全零，后是全1。

实际上，您不会使用此算法(将使用计数排序，如下所述)，但是它表明，如果可能的输入数量很多，您确实可以使用基于比较的算法击败Ω(n log n)。该算法很小。

已知某些基于比较的排序算法可在具有多个重复值的输入上非常快速地工作。例如，众所周知 Quicksort with a special partitioning step可以利用输入数组中重复的元素。

非比较排序

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

例如，如果您知道输入值是从仅具有| 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 |)中运行的 radix sort来做得更好。如果要处理原始 int，则lg | U |通常是32或64，因此速度非常快。如果您愿意实现一个特别棘手的数据结构，则可以利用 van Emde Boas Tree在O(n lg lg U)的时间O(n lg lg U)的范围内对0到U-1的整数进行排序，这又一次利用了整数由以下几组位组成的事实:可以分块进行操作。

同样，如果您知道元素是字符串，则可以通过在字符串中构建 trie来进行快速排序，然后遍历trie来重建所有字符串。另外，您可以将字符串视为数字，并以较大的基数(例如，ASCII文本的基数为128)编写，然后使用上面的整数排序算法之一。

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

希望这可以帮助!