std :: next_permutation的摊销复杂度？

std :: next_permutation的摊销复杂度？

所以看起来我将肯定地回答我自己的问题- 是 ，

next_permutation

在O（1）摊销时间内运行。

在我正式证明这一点之前，先快速回顾一下算法的工作原理。首先，它从范围的结尾向后扫描，直到开始，从而确定在最后一个元素处结束的范围中最长的连续递减子序列。例如，在中

03 4 2 1

，算法会将其标识

4 21

为该子序列。接下来，它查看此子序列之前的元素（在上面的示例中为3），然后找到子序列中大于它的最小元素（在上面的示例中为4）。然后交换这两个元素的位置，然后反转识别的序列。因此，如果我们从开始

03 4 2 1

，我们将3和4交换为yield

0 4 3 2 1

，然后将最后三个元素反转为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 =
O（1）。我们最终将范围末尾的最长递减序列的长度减少为长度1，因为反转末尾的递减序列会使范围的最后一个元素按升序排序。这意味着我们的电势从Φ=
3m变为Φ’= 3 * 1 =3。因此，电势的净下降为3-3m，因此我们的净摊销时间为3m +1 +（3-3m）= 4 =
O（1）。我们最终将范围末尾的最长递减序列的长度减少为长度1，因为反转末尾的递减序列会使范围的最后一个元素按升序排序。这意味着我们的电势从Φ=
3m变为Φ’= 3 * 1 =3。因此，电势的净下降为3-3m，因此我们的净摊销时间为3m +1 +（3-3m）= 4 = O（1）。

在前面的分析中，我简化了所有值都是唯一的假设。就我所知，为了使此证明有效，此假设是必要的。我将考虑一下，看看是否可以修改证明以在元素可以包含重复项的情况下工作，并且在详细研究完之后，我将对此答案进行编辑。