我只读了this other question about the complexity of next_permutation，虽然对响应(O(n))感到满意，但似乎该算法可能具有不错的摊销分析，显示出较低的复杂性。有人知道这样的分析吗？
最佳答案
因此，看起来我将肯定地回答我自己的问题-是，next_permutation在O(1)摊销时间内运行。
在我正式证明这一点之前，这里快速回顾一下算法的工作原理。首先，它从范围的结尾向后扫描，直到开始，从而确定在最后一个元素处结束的范围内最长的连续递减子序列。例如，在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。
为了证明该算法在摊销O(1)中运行，我们将使用电位方法。将Φ定义为序列末尾最长连续递减子序列长度的三倍。在此分析中，我们将假定所有元素都是不同的。鉴于此，让我们考虑一下该算法的运行时间。假设我们从序列的末尾开始向后扫描，发现最后m个元素是递减序列的一部分。这需要m +1个比较。接下来，我们发现该序列中的元素比该序列之前的元素大最小。在最坏的情况下，使用线性扫描进行另外m次比较会花费与递减序列的长度成比例的时间。交换元素需要花费1个信用点的时间，然后反转顺序最多需要进行m个以上的操作。因此，此步骤的实际运行时间约为3m +1。但是，我们必须考虑电势的变化。反转长度为m的序列后，最终将范围末端的最长递减序列的长度减少为长度1，因为反转末端的递减序列会使范围的最后一个元素按升序排序。这意味着我们的电势从Φ= 3m变为Φ'= 3 * 1 =3。因此，电势的净下降为3-3m，因此我们的净摊销时间为3m +1 +(3-3m)= 4 = O(1)。
在前面的分析中，我简化了所有值都是唯一的假设。就我所知，为了使此证明有效，此假设是必要的。我将考虑一下，看看是否可以修改证明以在元素可以包含重复项的情况下使用，一旦详细研究了细节，我将对此答案发布编辑。