置换算法的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！）？如果是这样的话！接管，使其变为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接近无穷大时，我们将分配的数量乘以排列的总数。

我们有：

展开sigma：

和的极限是极限的和：

此时，我们将评估极限和所有条件，除了第一个塌陷为零。由于我们的结果是一个常数，因此我们得到每个排列的复杂度为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)的相同原因）。