std::next_permutation 的摊销复杂度?
我刚刚阅读了另一个关于next_permutation 的复杂性，虽然我对响应(O(n))感到满意，但似乎该算法可能有一个很好的摊销分析，显示出较低的复杂性.有人知道这样的分析吗?
I just read this other question about the complexity of next_permutation and while I'm satisfied with the response (O(n)), it seems like the algorithm might have a nice amortized analysis that shows a lower complexity. Does anyone know of such an analysis?
推荐答案
所以看起来我将肯定地回答我自己的问题 - 是的，next_permutation 运行时间为 O(1) 分摊时间.
So looks like I'm going to be answering my own question in the affirmative - yes, next_permutation runs in O(1) amortized time.
在我正式证明这一点之前，这里有一个关于算法如何工作的快速复习.首先，它从范围的末尾向开始向后扫描，识别范围中以最后一个元素结尾的最长连续递减子序列.例如，在 0 3 4 2 1 中，算法会将 4 2 1 识别为这个子序列.接下来，它查看这个子序列之前的元素(在上面的例子中，3)，然后在子序列中找到比它大的最小元素(在上面的例子中，4).然后，它交换这两个元素的位置，然后反转识别的序列.因此，如果我们从 0 3 4 2 1 开始，我们将交换 3 和 4 以产生 0 4 3 2 1，然后将最后三个元素反转产生 0 4 1 2 3.
Before I go into a formal proof of this, here's a quick refresher on how the algorithm works. First, it scans backwards from the end of the range toward the beginning, identifying the longest contiguous decreasing subsequence in the range that ends at the last element. For example, in 0 3 4 2 1, the algorithm would identify 4 2 1 as this subsequence. Next, it looks at the element right before this subsequence (in the above example, 3), then finds the smallest element in the subsequence larger than it (in the above example, 4). Then, it exchanges the positions of those two elements and then reverses the identified sequence. So, if we started with 0 3 4 2 1, we'd swap the 3 and 4 to yield 0 4 3 2 1, and would then reverse the last three elements to yield 0 4 1 2 3.
为了表明该算法在分摊 O(1) 中运行，我们将使用潜在方法.将 Φ 定义为序列末尾最长连续递减子序列长度的三倍.在此分析中，我们将假设所有元素都是不同的.鉴于此，让我们考虑一下该算法的运行时间.假设我们从序列的末尾向后扫描，发现最后 m 个元素是递减序列的一部分.这需要 m + 1 次比较.接下来，我们找到该序列的元素中，哪个元素比该序列之前的元素大.这在最坏情况下花费的时间与使用线性扫描的递减序列的长度成比例，用于另一个 m 比较.交换元素需要花费 1 个学分的时间，然后反转序列最多需要 m 个更多的操作.因此，这一步的实际运行时间大约为 3m + 1.但是，我们必须考虑电位的变化.在我们反转这个长度为 m 的序列之后，我们最终将范围末尾的最长递减序列的长度减少为长度 1，因为反转末尾递减的序列会使范围的最后一个元素按升序排序.这意味着我们的电位从 Φ = 3m 变为 Φ' = 3 * 1 = 3.因此，电位的净下降为 3 - 3m，因此我们的净摊销时间为 3m + 1 + (3 - 3m) = 4 =复杂度(1).
To show that this algorithm runs in amortized O(1), we'll use the potential method. Define Φ to be three times the length of the longest contiguously decreasing subsequence at the end of the sequence. In this analysis, we will assume that all the elements are distinct. Given this, let's think about the runtime of this algorithm. Suppose that we scan backwards from the end of the sequence and find that the last m elements are part of the decreasing sequence. This requires m + 1 comparisons. Next, we find, of the elements of that sequence, which one is the smallest larger than the element preceding this sequence. This takes in the worst case time proportional to the length of the decreasing sequence using a linear scan for another m comparisons. Swapping the elements takes, say, 1 credit's worth of time, and reversing the sequence then requires at most m more operations. Thus the real runtime of this step is roughly 3m + 1. However, we have to factor in the change in potential. After we reverse this sequence of length m, we end up reducing the length of the longest decreasing sequence at the end of the range to be length 1, because reversing the decreasing sequence at the end makes the last elements of the range sorted in ascending order. This means that our potential changed from Φ = 3m to Φ' = 3 * 1 = 3. Consequently, the net drop in potential is 3 - 3m, so our net amortized time is 3m + 1 + (3 - 3m) = 4 = O(1).
在前面的分析中，我做了一个简化的假设，即所有值都是唯一的.据我所知，这个假设是必要的，以便这个证明可以工作.我会仔细考虑一下，看看是否可以修改证明以在元素可能包含重复项的情况下工作，一旦我完成了详细信息，我将发布对此答案的编辑.
In the preceding analysis I made the simplifying assumption that all the values are unique. To the best of my knowledge, this assumption is necessary in order for this proof to work. I'm going to think this over and see if the proof can be modified to work in the case where the elements can contain duplicates, and I'll post an edit to this answer once I've worked through the details.
相关文章