置换算法的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排列时间permute,使您的总时间复杂度为permute=O(1)

你的最终时间复杂度并没有减少到a == b,因为O(N)它仍然比一个数量级大O(1),并且只有常数项被删除(同样的原因O(N)).