我认为这应该可行，但请仔细检查细节。我们将原始数组中的一个元素称为 a[i]，将前缀数组中的一个元素称为 p[i]，其中 i 是各个数组的第 i 个元素。
\n\n因此，假设我们位于 a[i]，并且我们已经计算了 p[i] 的值。有三种可能的情况。如果 a[i] == a[i+1]，则 p[i] == p[i+1]。如果 a[i] < a[i+1]，则 p[i+1] >= p[i] + 1。这就剩下 a[i] > a[i+1] 的情况。在这种情况下，我们知道 p[i+1] >= p[i]。
\n\n在 na\xc3\xafve 情况下，我们返回前缀并开始计算小于 a[i] 的项目。然而，我们可以做得更好。首先，认识到 p[i] 的最小值为 0，最大值为 i。接下来看一下索引 j 的情况，其中 i > j。如果 a[i] >= a[j]，则 p[i] >= p[j]。如果 a[i] < a[j]，则 p[i] <= p[j] + j 。因此，我们可以开始向后通过 p 更新 p[i]_min 和 p[i]_max 的值。如果 p[i]_min 等于 p[i]_max，那么我们就有了解决方案。
\n\n对算法进行全面分析，它具有 O(n) 最佳情况性能。这是列表已经排序的情况。最坏的情况是逆序排序。那么性能就是O(n^2)。平均性能将为 O(k*n)，其中 k 是需要回溯的程度。我的猜测是对于随机分布的整数，k 会很小。
\n\n我也非常确定，对于部分排序数据的情况，会有一些方法来优化该算法。我会向Timsort寻求一些关于如何做到这一点的灵感。它使用运行检测来检测部分排序的数据。因此，该算法的基本思想是遍历列表一次并查找数据运行。对于升序运行的数据，您将遇到 p[i+1] = p[i]+1 的情况。对于降序运行，p[i] = p_run[0]，其中 p_run 是运行中的第一个元素。
\n| 归档时间： |
|
| 查看次数： |
225 次 |
| 最近记录： |