对于给定的 N 个实数数组，每个数字都有自己的键，但键不一定不同。众所周知，我们有 k 个不同的密钥。
当 k=O(log N) 时，我需要在 O(N log (log N)) 复杂度中找到一个稳定的排序算法，我可以使用 O(N) 的额外空间吗？
我什么都试过了，我什么都想不出来。
问问题
7001 次
5 回答
3
正如 Tilman Vogel 指出的那样，通过对输入数据施加特定限制，理论上可以以 Θ(n log(log n)) 复杂度运行的算法。似乎它们不太可能在大多数实际应用程序中提供很大的好处，这可能是我从未见过实现的原因，但如果它们适合您的用例，我很想知道这些算法是否能更快地进行基准测试。
这是 Steven S. Skiena 的算法设计手册的摘录，解释了为什么不可能提出通用的 Θ(n log(log n)) 排序算法：
我们已经看到了几种在最坏情况 O(n log n) 时间内运行的排序算法，但它们都不是线性的。对 n 个项目进行排序当然需要查看所有项目，因此任何排序算法在最坏的情况下都必须是 Ω(n)。我们可以缩小这个剩余的 Θ(log n) 差距吗？
答案是不。Ω(n log n) 下限可以通过观察任何排序算法在每个不同的 n! n 个键的排列。每个成对比较的结果控制着任何基于比较的排序算法的运行时行为。我们可以将这种算法的所有可能执行的集合想象成一棵树，其中有 n! 树叶。最小高度树对应于最快的算法，它恰好 lg(n!) = Θ(n log n)。
于 2013-06-11T10:53:27.727 回答
1
http://en.wikipedia.org/wiki/Sorting_algorithm声称 Han 和 Thorup 的算法具有您所需的复杂性。
于 2013-06-11T10:26:52.977 回答
1
为了达到这个界限，我们必须考虑树，特别是二叉搜索树。存在一类二叉搜索树，在节点中有一些额外的信息，如父、左子、右子和颜色……是的，我说的是红黑树。在RB树中插入一个节点的时间复杂度是O(log n)，n是树的节点数。基本思想是遍历数组，插入RB树中的每一个元素，但是有一个约束，如果我们检测到重复的元素，不要插入！！！，只计算！怎么做？很简单，只需在节点中添加一个字段“count”，每次找到重复元素时只需增加计数器，但不要作为新节点插入。这样做，RB 树将只有 O(k) 个元素，即，对于我们的示例，O(log n)。所以在 RB 树中插入一个节点的复杂度是 O(log (log n))。一旦我们在 RB 树中插入所有元素，时间复杂度将为 O(n log (log n))。下一步是按顺序遍历树！！，并复制每个元素，使得计数器是。这样做我们得到了排序数组（RB 树是二叉搜索树），并且因为按顺序遍历的时间复杂度是 O(n)，所以总体时间复杂度将是 O(n log (log n))。
于 2015-09-08T18:10:17.103 回答
0
我们正在处理比较模型，而不是单词 ram 模型。众所周知，我们无法通过下界n log h，其中n是输入大小，h是容器中元素的数量。在排序算法中，我们可以通过任何平衡二叉搜索树来实现上界，包括RBT和AVL以及优先队列（笛卡尔树排序）。
在这种情况下，关键是所选容器的大小不能大于h = k = log n（我们说h = n一般是因为通用性）。本质上，raul_zevahc 得到了这个想法，我们只需要稍微修改解决方案即可实现稳定排序。我们没有为每个节点维护一个队列（先进先出），而不是实际计算集合中元素的数量。每当遍历一个节点时，我们都会弹出该节点的所有元素。
对于不稳定的排序算法，我们总是可以将其更改为稳定的排序算法，代价是线性时间预处理。
于 2018-07-08T19:12:47.147 回答
0
你们正在考虑“传统”排序算法（冒泡、合并、快速等），而他描述的原始算法基本上是对 BucketSort 或 RadixSort 的描述。这些不属于 Ω(nlogn) 限制，因为它们不执行二进制比较，而是根据要排序的项目数进行比较！
我只能猜测对于要排序的 n 个项的键或值的多对数的 Radixsort 形式可以具有所需的复杂性。但是我不能 100% 确定，因为我没有测试过也没有证明过。
于 2017-04-19T00:09:42.483 回答