置换计算运行时复杂度的一些变化

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))语句。每运行一次这行，它就遍历列表，它遍历整个列表，这就是复杂性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)上迭代。你知道吗