排列生成算法时间复杂度辨析：O(n!)与O(n*n!)哪个正确？

结论 #

《Elements of Programming Interviews》给出的 O(n×n!) 是正确结论，你的推导存在两处关键遗漏导致结果偏差。

你的推导问题说明 #

• 第一，错误估算了单步操作的类型和开销：Collections.swap 是交换列表中两个下标的元素，属于O(1)的常数操作，不是你以为的O(n)操作，非叶子节点的所有swap操作总时间加总只有O(n!)量级，并不是时间复杂度的主导项。
• 第二，完全遗漏了base case里的数组复制开销：当递归到终止条件A.size()-1==start时，你执行了result.add(new ArrayList<>(A))，这一步会完整复制长度为n的当前排列，是O(n)的时间操作。而排列总共有n!个，仅这部分的总时间开销就达到了O(n×n!)，是整个算法的时间主导项。

书中的推导逻辑完全成立：总函数调用次数是O(n!)，每次调用要么做常数级的swap操作，要么做O(n)的数组复制，整体时间上界就是O(n×n!)。

额外补充空间复杂度的问题 #

你的空间复杂度推导也存在偏差：

• 如果你把存储结果的空间算入统计，n!个排列每个占n个元素的空间，总空间是O(n×n!)；
• 如果只算算法运行的辅助空间（不算输出结果），只有递归栈的开销，递归深度等于数组长度n，所以辅助空间是O(n)。

你之前提到的O(max(n!, n))不成立，n!是排列的数量，每个排列占n个存储位，不能直接拿n!作为空间量级。

内容的提问来源于stack exchange，提问作者super.t