python-3.x - 置换算法的Big-O分析

Question

result = False
def permute(a,l,r,b):
    global result
    if l==r:
        if a==b:
            result = True
    else:
        for i in range(l, r+1):
            a[l], a[i] = a[i], a[l]
            permute(a, l+1, r, b)
            a[l], a[i] = a[i], a[l]

string1 = list("abc")
string2 = list("ggg")
permute(string1, 0, len(string1)-1, string2)

所以基本上我认为找到每个排列需要 n^2 步(乘以某个常数)并且找到所有排列应该需要 n!脚步。那么这会使它成为 O(n^2 * n!) 吗？如果是的话 n!接管，让它只是 O(n!)？

谢谢

编辑:这个算法对于寻找排列可能看起来很奇怪，那是因为我还用它来测试两个字符串之间的字谜。抱歉，我还没有重命名该方法

Answer 1

找到每个排列不需要 O(N^2)。在 O(1) 时间内创建每个排列。虽然说这个 O(N) 很诱人，因为您为每个排列 N 次为每个索引分配了一个新元素，但每个排列与其他排列共享分配。

当我们这样做时:

a[l], a[i] = a[i], a[l]
permute(a, l+1, r, b)

permute 的所有后续递归调用都已完成此分配。

实际上，赋值只会在每次调用 permute 时发生，即 次。然后我们可以使用一些极限演算来确定构建每个排列的时间复杂度。当 N 接近无穷大时，我们将分配的数量与排列总数相比较。

我们有:

扩展西格玛:

总和的极限是极限的总和:

在这一点上，我们评估我们的极限和除第一个坍缩为零之外的所有项。由于我们的结果是一个常数，我们得到每个排列的复杂度是 O(1)。

但是，我们忘记了这部分:

if l==r:
    if a==b:
        result = True

a == b(两个列表之间)的比较发生在 O(N) 中。构建每个排列需要 O(1)，但我们在最后对每个排列进行的比较实际上需要 O(N)。这为我们提供了每个排列的 O(N) 的时间复杂度。

这为您提供 N! 个排列时间 O(N)，每个排列的总时间复杂度为 O(N!) * O(N ) = O(N * N!)。

您的最终时间复杂度不会降低到 O(N!)，因为 O(N * N!) 仍然比 大一个数量级>O(N!)，并且只有常数项被删除(与 O(NlogN) != O(N) 相同的原因)。