sorting - 功能样式中最快的排序

Question

作为一名本科生，我研究了 O(n log n) 排序算法，并证明当我们所能做的就是比较 2 个数字时，我们不能在一般情况下做得更好。那是针对随机存取存储器的计算模型。我想知道函数式(引用透明)程序是否存在这种理论下限。让我们假设每个 beta 减少算作一个步骤，每个比较都算作一个步骤。

Answer 1

因此，让我们假设您同意在一般情况下我们不能比 (n*log n) 做得更好的证明，在这种情况下我们唯一拥有的就是比较。

所以问题是我们是否可以证明我们可以在没有副作用的情况下做同样的事情。

这样做的一种方法是，如果您可以在 O(n*log n) 中构建一个不可变的二叉搜索树，然后中缀遍历它(可以在 O(n) 中完成)，那么我们将有一种排序算法。

如果我们可以遍历所有项目并将每个项目添加到平衡的不可变(持久)树中，时间复杂度为 O(log n)，则算法复杂度为 O(n*log n)。

我们可以在 O(log n) 中添加到持久二叉树吗？当然，在持久数据结构库的每个合理实现中，都有 O(log n) 插入的平衡二叉搜索树的不可变变体。

为了理解为什么它是可能的，想象一个标准的平衡二叉搜索树，例如红黑树。您可以按照与可变版本相同的算法来制作它的不可变版本，除非指针或颜色发生变化时，您需要分配一个新节点，然后将其所有父节点分配给根节点(同时在必要时也转换它们) .不改变的侧枝得到重用。最多有 O(log n) 个受影响的节点，因此每次插入最多有 O(log n) 个操作(包括分配)。如果您了解红黑，您会发现除了常数之外没有其他乘数(对于轮换，您可以为受影响的 sibling 获得一些额外分配，但这仍然是一个常数因子)。

这个 - 非常非正式的 - 演示可以让您了解 O(n*log n) 的排序证明存在而没有副作用。但是，还有一些我遗漏的东西。例如。分配在这里被认为是 O(1)，这可能并非总是如此，但那样会变得太复杂。