algorithm - 为什么置换算法的时间复杂度是 n*n！而不是 n^3 * n!?

Question

作者声称这种置换算法的时间复杂度：

from collections import deque

def find_permutations(nums):
    
    nums_l = len(nums)
    perms = deque()
    perms.append([])
    
    for num in nums:                     # (1)
        for _ in range(len(perms)):      # (2)
            perm = perms.popleft() 
            for j in range(len(perm)+1): # (3)
                new_perm = list(perm)    # (4)
                new_perm.insert(j, num)  # (5)
                perms.append(new_perm)   # (6)
    
    return perms

是n*n!

但我不明白为什么。这是我对每行代码的时间复杂度的计算：

(1): len(nums) ~ n
(2): len(perms) ~ n!
(3): len(perm) ~ n
(4): n
(5): n
(6): n

所以总时间复杂度为：

n * n! * n * (n + n + n) ~ n^3 * n!

我错了吗？

标签： algorithmtime-complexitypermutation

Answer 1

在讨论主要问题之前，步骤 (6) 有一个小错误：append是 O(1)。但这并不影响整体的复杂性。

您的分析在第 (2) 步出错：

for _ in range(len(perms)):

这不会执行 O(n!) 次迭代。第一次它甚至只执行1次迭代，第二次还是1次迭代，第三次2次迭代，然后是2 * 3，然后是2 * 3 * 4，……最后一次（n-1）！迭代。

那么在第（3）步也有高估：

for j in range(len(perm)+1)

的大小perm最初很小（对应于步骤 2 的循环）：首先排列的大小为 0，然后在外循环的下一次迭代中，它们的大小为 1，...然后 2，...向上为 n-1。

所以对于内部循环的总迭代次数，我们有这个总和：

1 * 1 + 1 * 2 + 2 * 3 + (2 * 3) * 4 + ... + k！+ ... 嗯！

一种更简单的方法是认识到，在外循环的每次迭代中，这段代码都会产生比其前一次迭代长一个项目的所有排列。因此，在第一次迭代中，您获得所有大小为 1 的排列（使用第一个输入值），在第二次迭代中，您获得所有大小为 2 的排列（使用两个第一个输入值），......等等。这是一种自下而上的方法。另请注意，popLeft执行正确的次数以删除先前（外部）迭代的所有排列，而append针对所有新排列（仅在下一次外部迭代中弹出）执行。

所以我们现在可以很容易地看到它append被执行了这么多次：

1！+ 2！+ 3！+ 4！+ ... + n！= O(n!)

如果我们现在将步骤 4 的复杂性包括在内（它“吸收”了步骤 5 的复杂性），那么我们得到：

1.1！+ 2.2！+ 3.3！+ 4.4！+ ... + 嗯！= O(nn!)