algorithm - 对数组有约束的排序算法

Question

我正在尝试提出一种算法，可以在 O(nlog(logn)) 时间内对 A 进行排序和排列。其中 A[0...n-1] 具有属性 A[i] >= A[i-j] 对于所有 j >= log(n)。

到目前为止，我已经考虑将 A 划分为每个 logn 大小的 block 。

那么我认为第一个 block 会比它后面的 block 小得多吗？

我想我遗漏了其中的一部分。

Answer 1

Tree Sort将是这里的一个选项。您从数组的左端开始并将元素馈送到树中。每当你的树有超过 log(n) 个元素时，你就取出最小的元素，因为你确定所有后续元素都更大，并将其放回排序数组中。这样树的大小总是 log(n)，树操作的成本是 log(log(n))。事实上，您只需要操作 (1) 插入随机元素和 (2) 删除最小元素，因此您不一定需要树，而是任何类型的 priority queue。会为此目的做的。这样平均和最坏情况下的性能都能满足您的要求。