PCF Learned Sort: a Learning Augmented Sort Algorithm with O(n loglog n) Expected Complexity
Atsuki Sato and Yusuke Matsui
排序是计算机科学中最基础的算法之一。近年来，使用机器学习提升排序速度的Learned Sort引起了广泛关注。虽然现有研究表明Learned Sort在实证上比经典排序算法更快，但它们并未提供关于其计算复杂度的理论保证。我们提出了分段常数函数（PCF）Learned Sort，一种具有理论保证的Learned Sort算法。我们证明了在对数据分布进行温和假设的前提下，PCF Learned Sort的期望复杂度为𝒪(n loglog n)。我们还在合成数据集和真实数据集上实证确认了PCF Learned Sort具有𝒪(n loglog n)的计算复杂度。这是首个从理论上支持Learned Sort实证成功的研究，并为解释Learned Sort为何快速提供了证据。代码可在https://github.com/atsukisato/PCF_Learned_Sort获取。
Sorting is one of the most fundamental algorithms in computer science. Recently, Learned Sorts, which use machine learning to improve sorting speed, have attracted attention. While existing studies show that Learned Sort is empirically faster than classical sorting algorithms, they do not provide theoretical guarantees about its computational complexity. We propose Piecewise Constant Function (PCF) Learned Sort, a theoretically guaranteed Learned Sort algorithm. We prove that the expected comple...