.png){kind=icon}
返回
Fast and Simple Sorting Using Partial Information
.png){kind=icon}
PRE
AI
DOI：10.1007/s00453-026-01387-3.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
考虑给定m次预先比较结果的n个物品排序问题。我们提出了一种简单自然的确定性算法，运行时间为O(m+logT)，并进行O(logT)次比较，其中T是与预先比较结果一致的总体排序数量。我们的运行时间和比较界限在常数因子范围内是最优的，从而解决了自1976年Fredman（理论计算机科学）以来一直被深入研究的问题。之前最佳的比较次数界限为O(logT)的算法，其时间复杂度为O(n^2.5)且更为复杂。我们的算法结合了三种经典算法：拓扑排序、特定堆结构的堆排序以及在有序列表中的高效搜索。它按排序顺序逐个输出物品。该算法可修改为提前终止，从而解决重要且更一般的top-k排序问题：给定k和某些预先比较结果，按排序顺序输出最小的k个物品。修改后的算法在时间和比较次数上解决了top-k排序问题，在常数因子范围内达到最优。
Keyword:
Sorting under partial information
Partial orders
Topological sort
Working-set heaps
期刊
A
IF:
0.7
论文数:
56
被引数:
2.7K
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏
分享收藏
查看更多内容