排序算法的“Ω（n log n）障碍”的规则是什么？

  • Z时代
  • 2024-01-10
  • 分类：问答

我写了一个简单的程序，排序为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）吗？

回答：

要直接回答您的问题：

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

  2. 这不是问题；实际上，这是一种著名的排序算法的特例，它打破了Ω（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]。更一般而言，在最佳情况下，算法进行的每个比较都可以根据比较结果将算法置于两个新状态之一。因此，我们可以想到一个描述该算法可能处于的状态的大型二叉树结构-

每个状态最多包含两个子对象，这些子对象根据进行的比较结果描述该算法进入的状态。如果我们采取从树的根部到叶子的任何路径，我们得到了一系列比较，这些比较最终由算法在特定输入上进行。为了尽可能快地进行排序，我们希望使比较的次数最少，因此我们希望此树结构的高度尽可能小。

现在，我们知道两件事。首先，我们可以将算法可以进入的所有状态视为二叉树。其次，该二叉树必须至少具有f（n）个不同的节点。鉴于此，我们可以构建的最小的二叉树必须具有至少Ω（log

f（n））的高度。这意味着，如果有f（n）种可能的对数组元素进行排序的方式，

，因为否则我们将无法进入足够的不同状态。

要总结证明您无法击败Ω（n log n）的证明，请注意，如果数组中包含n个不同的元素，那么就有n个！元素排序的不同可能方式。使用

，我们得到该log

n！=Ω（n log n），因此我们必须在平均情况下至少进行Ω（n log n）比较才能对输入序列进行排序。

回答：

在上面看到的内容中，我们看到，如果您拥有n个完全不同的数组元素，则无法使用比较排序对它们进行排序的速度快于Ω（n log

n）。但是，此初始假设不一定有效。我们想要排序的许多数组中可能包含重复的元素。例如，假设我要对仅由零和一组成的数组进行排序，例如此处的数组：

 0 1 0 1 1 1 0 0 1 1 1

在这种情况下， 不 存在n！不同的零数组和长度为n的数组。实际上，它们只有2

n个。根据上面的结果，这意味着我们应该能够使用纯基于比较的排序算法对Ω（log 2 n）=Ω（n）进行排序。实际上，我们绝对可以做到；这是我们如何做的草图：

  1. 看第一个元素。

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

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

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

  5. 将这三个数组的所有三个以较小，相等，较大的顺序连接在一起。

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

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

已知某些基于比较的排序算法可在具有多个重复值的输入上非常快速地工作。例如，已知具有特殊分区步骤的Quicksort可以利用输入数组中重复的元素。

回答：

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

例如，如果您知道输入值是从仅具有| 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

|）运行的基数排序来做得更好。如果要处理原始ints，则lg |

U | 通常是32或64，因此速度非常快。如果您愿意实现特别棘手的数据结构，则可以利用整数由组组成的事实，使用van Emde

Boas树在O（n lg lg U）的时间O（n lg

lg U）的范围内对从0到U-1的整数进行排序。可以按块操作的位。

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

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

希望这可以帮助！

以上是 排序算法的“Ω（n log n）障碍”的规则是什么？ 的全部内容， 来源链接： utcz.com/qa/413320.html

回到顶部