性病的摊销复杂:: next_permutation？ [英] The amortized complexity of std::next_permutation?

问题描述

我刚才读<一href="http://stackoverflow.com/questions/4972470/what-is-the-time-complexity-of-stdnext-permutation-function-in-c">this关于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 then 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个比较。下一步，我们发现，序列，其中一个是比元件preceding此序列的最小较大的要素。这需要在最坏情况下的时间与使用另一米比较的线性扫描的递减序列的长度。交换的元素需要，比如，时间1个学分的价值，并扭转序列，然后要求，至多m更多的操作。因此该步骤的运行时间实际是大致3米+ 1。然而，我们必须在电位变化到因素。之后，我们扭转长度为m的这个序列，我们最终减少最长下降序列的长度范围的结束是长度为1，因为扭转衰减序列在年底使范围内的按升序排序的最后一个元素。这意味着，我们的潜力，从与披改变; = 3M公司＆披; = 3 * 1 = 3。结果，在潜在的净降是3 - 3米，所以我们的净平摊时间为3m + 1 +。（3 - 3米）= 4 = O（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'll 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).

在preceding分析，我做了简化假设，即所有的值都是唯一的。尽我所知，这个假设是必要的，为了这个证明工作。我要想一想，看看是否证明可以被修改的情况下工作，其中的元素可以包含重复的，我会后编辑这个答案一旦我通过细节工作。

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.

这篇关于性病的摊销复杂:: next_permutation？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！