论文标题
部分可观测时空混沌系统的无模型预测
Efficient Algorithms for Sorting in Trees
论文作者
论文摘要
排序是计算机科学中通常用于序列或总订单的基本问题。最近，已经研究了对部分有序的集合（或POSET）进行分类的更通用的形式，其中一些元素是无与伦比的。通用POSET排序算法的较低查询复杂性为$ω（wn + n \ log n）$，其中$ w $是poset的宽度。 我们考虑了在树木中进行分类的问题，一种特定的部分订单案例，并参数相对于$ d $，这是树木中元素的最大程度的复杂性，因为$ d $通常比树木中的$ w $小得多。例如，在完整的二进制树中，$ d =θ（1），w =θ（n）$。我们提出了一种随机算法，用于在最差的预期$ O（dn \ log n）$查询和时间复杂性中对树poset排序。这改善了$ o（dn \ log^2 n）$的先前上限。我们的算法是第一个对有限度树最佳的算法。我们还提供了$ω（DN + N \ log n）$的新下限，以解决对树poset排序的最差查询复杂性。最后，我们提出了第一个用于排序树poset的确定性算法，该算法的总复杂性低于现有算法用于对一般部分顺序排序的算法。
Sorting is a foundational problem in computer science that is typically employed on sequences or total orders. More recently, a more general form of sorting on partially ordered sets (or posets), where some pairs of elements are incomparable, has been studied. General poset sorting algorithms have a lower-bound query complexity of $Ω(wn + n \log n)$, where $w$ is the width of the poset. We consider the problem of sorting in trees, a particular case of partial orders, and parametrize the complexity with respect to $d$, the maximum degree of an element in the tree, as $d$ is usually much smaller than $w$ in trees. For example, in complete binary trees, $d = Θ(1), w = Θ(n)$. We present a randomized algorithm for sorting a tree poset in worst-case expected $O(dn\log n)$ query and time complexity. This improves the previous upper bound of $O(dn \log^2 n)$. Our algorithm is the first to be optimal for bounded-degree trees. We also provide a new lower bound of $Ω(dn + n \log n)$ for the worst-case query complexity of sorting a tree poset. Finally, we present the first deterministic algorithm for sorting tree posets that has lower total complexity than existing algorithms for sorting general partial orders.
