为什么置换算法的时间复杂度是n*n！而不是 n^3 * n!?
Why time complexity for permutation algorithm is n*n! and not n^3 * n!?
作者声称此排列算法的时间复杂度：
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!
我错了吗？
该算法通过将数字插入现有排列的所有可能位置来生成排列
现在第一个循环显然是O(n)
让我们看看其他循环发生了什么：
最后一次迭代（最坏情况）：
- 遍历所有
(n-1)! 排列（由之前的迭代生成）- O((n-1)!)
- 复制每一个并在其中添加新数字 -
O(n) 每个
在其他循环的最坏情况下总共 (n-1)! * (n) = n!
总的来说 O(n * n!)
在进入正题之前，第(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！ + ... n!
一种更简单的方法是认识到，在外循环的每次迭代中，这段代码产生的所有排列都比其前一次迭代长一个项目。因此，在第一次迭代中，您将获得大小为 1 的所有排列（使用第一个输入值），在第二次迭代中，您将获得所有大小为 2 的排列（使用两个第一个输入值），...等等。这是一种自下而上的方法。另请注意 popLeft 执行了正确的次数以删除先前（外部）迭代的所有排列，而 append 对所有新排列执行（仅在下一次外部迭代中弹出） .
所以我们现在可以很容易地看到 append 被执行了这个次数：
1个！ + 2！ + 3！ + 4！ + ... + n！ = O(n!)
如果我们现在将步骤 4 的复杂性包括在内（它“吸收”了步骤 5 的复杂性），那么我们得到：
1.1！ + 2.2！ + 3.3！ + 4.4！ + ... + n.n！ = O(n.n!)
作者声称此排列算法的时间复杂度：
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!
我错了吗？
该算法通过将数字插入现有排列的所有可能位置来生成排列
现在第一个循环显然是O(n)
让我们看看其他循环发生了什么：
最后一次迭代（最坏情况）：
- 遍历所有
(n-1)!排列（由之前的迭代生成）-O((n-1)!) - 复制每一个并在其中添加新数字 -
O(n)每个
在其他循环的最坏情况下总共 (n-1)! * (n) = n!
总的来说 O(n * n!)
在进入正题之前，第(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！ + ... n!
一种更简单的方法是认识到，在外循环的每次迭代中，这段代码产生的所有排列都比其前一次迭代长一个项目。因此，在第一次迭代中，您将获得大小为 1 的所有排列（使用第一个输入值），在第二次迭代中，您将获得所有大小为 2 的排列（使用两个第一个输入值），...等等。这是一种自下而上的方法。另请注意 popLeft 执行了正确的次数以删除先前（外部）迭代的所有排列，而 append 对所有新排列执行（仅在下一次外部迭代中弹出） .
所以我们现在可以很容易地看到 append 被执行了这个次数：
1个！ + 2！ + 3！ + 4！ + ... + n！ = O(n!)
如果我们现在将步骤 4 的复杂性包括在内（它“吸收”了步骤 5 的复杂性），那么我们得到：
1.1！ + 2.2！ + 3.3！ + 4.4！ + ... + n.n！ = O(n.n!)