自实现无重复排列生成算法的时间复杂度Big-O分析

核心结论 #

该算法的时间复杂度为 O(n·n!)，其中n为输入数组的长度。

推导过程 #

我们可以逐轮拆解算法的运行逻辑，结合每一步的数组操作成本，累加得到整体复杂度：

• 先明确算法的运行规律：外层循环一共执行n-1轮（i从0到n-2），每轮的状态有固定特征：
  • 第i轮迭代开始时，当前待拆分的排列总数为n!/(n-i)!，也就是固定前i个位置元素后，剩余位置的所有排列组合数
  • 对每个待拆分的排列，算法会取前i个元素作为固定前缀，对剩余长度为n-i的后缀做循环移位，生成n-i个新的排列
  • 全部迭代结束后，最终生成的排列总数恰好为n!，完全符合无重复全排列的数量预期
• 再核算单步操作的成本：代码中所有数组操作（slice切片、数组展开拼接、map遍历、flat拍平）的成本都和操作涉及的元素总数线性相关：
  • 每生成1个新的排列，需要完成长度为n的数组元素复制，单步成本为O(n)
  • 每轮迭代中，生成的新排列总数为 待拆分排列数 × 每个排列拆出的子排列数，即 (n!/(n-i)!) × (n-i) = n!/(n-i-1)!
• 最后做全量成本累加：把每一轮的总成本求和后可以发现，求和部分的结果是n!乘以一个趋近于常数的收敛级数（级数极限和自然常数e的展开项相关，和n的大小无关）。哪怕忽略所有低阶、常数级的开销，仅最后一轮迭代生成的n!个排列，就已经需要完成n×n!次元素复制操作，是整体成本的核心贡献项。

举个实际验证的例子：输入长度n=3时，手动核算全流程的数组元素复制次数一共为30次，对应量级为3×3! =18，和核心贡献项的规模一致，常数占比的固定开销会在Big-O计算时被忽略。

常见认知澄清 #

很多开发者会误将全排列算法的复杂度记为O(n!)，这个认知存在明显偏差：

• O(n!)是对“生成的排列总个数”的计数，没有考虑每个排列本身的存储、复制成本
• 只要算法最终输出的是完整的、长度为n的排列数组，仅将这些内容写入内存的硬成本就已经达到O(n·n!)，不存在比这个量级更低的、能输出完整排列的算法
• 本算法没有额外的嵌套冗余循环，所有操作都是沿排列生成的线性路径完成的，没有超出基础硬成本的额外开销。

内容的提问来源于stack exchange，提问作者M. Dollinger