python - 置换计算运行时复杂度有一些变化

Question

我对标准排列查找算法的运行时复杂性有疑问。考虑一个列表 A，查找(并打印)其元素的所有排列。

这是我的递归实现，其中 printperm() 打印每个排列:

def printperm(A, p):
    if len(A) == len(p):
        print("".join(p))
        return

    for i in range(0, len(A)):
        if A[i] != 0:
            tmp = A[i] # remember ith position
            A[i] = 0 # mark character i as used
            p.append(tmp) # select character i for this permutation
            printperm(A, p) # Solve subproblem, which is smaller because we marked a character in this subproblem as smaller
            p.pop() # done with selecting character i for this permutation
            A[i] = tmp # restore character i in preparation for selecting the next available character


printperm(['a', 'b', 'c', 'd'], [])

运行时复杂度似乎是 O(n!)，其中 n 是 A 的大小。这是因为在每个递归级别，工作量减少 1。因此，顶级递归级别是 n 工作量，下一层是n-1，下一层是n-2，依此类推。所以总的复杂度是 n*(n-1)*(n-2)...=n!

现在的问题是 print("".join(p)) 语句。这行代码每次运行的时候都会遍历list，也就是遍历整个list，复杂度为n。有 n!大小为 n 的列表的排列数。所以这意味着 print("".join(p)) 语句完成的工作量是 n!*n.

print("".join(p)) 语句的存在是否会将运行时复杂度增加到 O(n * n!)？但这似乎不对，因为我没有在每次递归调用时都运行 print 语句。我获得 O(n * n!) 的逻辑在哪里崩溃了？

Answer 1

你基本上是对的!可能的混淆来自您的“......下一个级别是 n-2，依此类推”。 “等等”在递归的最底层掩盖了这一点，你不是做 O(1) 工作，而是 O( n) 进行打印。所以总的复杂度正比于

n * (n-1) * (n-2) ... * 2 * n

等于n! * n。请注意，.join() 对此并不重要。它也需要 O(n) 的工作来简单地 print(p)。

编辑:但这并不正确，原因不同。在 print 级别之上的所有级别，您都在做

for i in range(0, len(A)):

和len(A) 没有改变。所以每个 级别都在做O(n) 的工作。可以肯定的是，级别越深，A 中的零越多，因此循环所做的工作越少，但它仍然是 O(n) 只是为了迭代完全超过 range(n)。