std :: next_permutation的摊销复杂性？

Question

我刚刚读到了关于next_permutation复杂性的另一个问题,虽然我对响应(O(n))感到满意,但似乎算法可能有一个很好的摊销分析,显示出较低的复杂性.有谁知道这样的分析？

Answer 1

所以看起来我将以肯定的方式回答我自己的问题 - 是的,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).

在前面的分析中,我做了一个简化的假设,即所有值都是唯一的.据我所知,这个假设是必要的,以便这个证明有效.我将考虑这一点,看看证明是否可以修改为在元素可以包含重复的情况下工作,并且一旦我完成了细节,我将发布一个编辑到这个答案.

Answer 2

我不确定std :: next_permutation的确切实现,但如果它与在这里wiki中描述的Narayana Pandita算法相同:http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations,

假设元素是不同的,看起来像是O(1)摊销!(当然,下面可能有错误)

让我们算一下完成的掉期总数.

我们得到了递归关系

T(n + 1)=(n + 1)T(n)+Θ(n ²)

(n + 1)T(n)来自固定第一个元素并对剩余的n进行交换.

Θ(n ²)来自改变第一个元素.在我们改变第一个元素的时刻,我们做Θ(n)交换.这样做n次,得到Θ(n ²).

现在让 X(n) = T(n)/n!

然后我们得到

X(n + 1)= X(n)+Θ(n ²)/(n + 1)!

即,有一些常数C这样

X(n + 1)<= X(n)+ Cn ² /(n + 1)!

写下这种不平等给了我们

X(n + 1) - X(n)<= Cn ² /(n + 1)!

X(n)-X(n-1)<= C(n-1)² /(n)!

X(n-1)-X(n-2)<= C(n-2)² /(n-1)!

...

X(2) - X(1)<= C1 ² /(1 + 1)!

添加它们给了我们X(n+1) - X(1) <= C(\sum j = 1 to n (j^2)/(j+1)!).

因为无限级数\sum j = 1 to infinity j^2/(j+1)!会聚到C',比方说,我们得到了X(n+1) - X(1) <= CC'

请记住,X(n)计算所需的交换平均数(T(n)/ n!)

因此,交换的平均数量是O(1).

由于找到要交换的元素与交换数量成线性关系,即使您考虑其他操作,也会进行O(1)摊销.