排列算法时间复杂度为何为n*n!而非n³*n!？对代码复杂度计算的疑问

首先，这个算法的核心逻辑是逐个插入元素生成全排列：每加入一个新元素，就把它插入到已有所有排列的每个可能位置上，最终得到所有n!个排列。你的计算问题出在把所有循环的规模都直接用最终的n或n!代替，但实际上每个阶段的队列长度、排列长度是逐步增长的，不是一开始就达到n或n!的量级。

1. 分阶段拆解循环次数 #

我们把外层循环（标记(1)）的每一轮看作一个阶段：处理第k+1个元素时（k从0到n-1）：

• 队列perms里的排列数量是k!（前k个元素已经生成了k!个全排列），所以内层循环(2)的执行次数是k!，不是n!。
• 每个已有排列的长度是k，所以循环(3)的执行次数是k+1（插入到排列的k+1个位置），不是n。

2. 单次操作的时间复杂度 #

再看你标记的(4)(5)(6)：

• (4)复制排列：当前排列长度是k，所以时间复杂度是O(k)，不是O(n)。
• (5)插入元素：列表插入操作需要移动后续元素，当前排列长度是k，所以时间复杂度是O(k)，不是O(n)。
• (6)队列追加元素：deque.append()是**均摊O(1)**操作，不是O(n)。

所以单次循环(3)的总时间是O(k)，不是你估算的O(n+n+n)。

3. 总时间复杂度计算 #

现在把每个阶段的时间加起来：
第k阶段（处理第k+1个元素）的时间是：
k! * (k+1) * O(k) = O(k*(k+1)!)

我们需要对k从0到n-1求和：
总时间 = O(Σ(k*(k+1)!))，其中k从0到n-1

接下来化简这个求和式：
利用恒等式 k*(k+1)! = (k+2)! - 2*(k+1)!，展开求和后可以得到：
Σ(k*(k+1)!) = (n+1)! - Σ((k+1)!)，其中k从0到n-1

而Σ((k+1)!)从0到n-1是1!+2!+...+n!，这个和远小于n*n!（因为n!是主导项，后面的项加起来不超过n!的2倍）。而(n+1)! = (n+1)*n! = O(n*n!)，所以整个求和式的量级是O(n*n!)。

结论 #

所以作者声称的时间复杂度O(n*n!)是正确的，你的计算错误在于忽略了循环规模的阶段性增长，以及错误估计了单次操作的时间量级。

内容的提问来源于stack exchange，提问作者illuminato