排列函数时间复杂度分析：是T((n!)²)还是T(n*n!)？

问题描述 #

给定一个由不同整数组成的nums数组，返回所有可能的排列。例如，[1,2,3]的排列为：

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

我写了一段JavaScript实现，和标准解法类似。但我发现很多资料说它的时间复杂度是T(n*n!)，可我觉得应该是T((n!)²)，可能我的理解有问题。

JavaScript实现 #

var permute = function(nums) {
    if(nums.length === 0) return [];
    if(nums.length ===1) {
        return [[...nums]]; 
    }
    
    let results = [];
    const len = nums.length;
    for (let i=0; i<len; i++) {
        // eg: [1,2,3,4]
        const temp = nums[i]; 
        nums[i] = nums[len-1]; 
        nums[len-1] = temp; // [4,2,3,1]
        const n = nums.pop(); // [4,2,3]
        const prems = permute(nums);
        prems.forEach(perm => perm.push(n));
        results = results.concat(prems); 
        nums.push(nums[i]) // [4,2,3,4]
        nums[i] = temp; // [1,2,3,4]
    }
    
    return results;
};

我的推导过程 #

我得出时间复杂度为T((n!)²)的依据如下：

• 外层首次循环：
  • 每次迭代会对长度为n-1的数组进行递归调用
  • 递归返回的排列结果数量为(n-1)!
  • 需要遍历(n-1)!个元素，将弹出的元素追加到每个排列中
• 外层循环共执行n次，因此首次递归调用的时间开销为T(n*(n-1)!)
• 递归树的规模为n!，因此最终时间复杂度应为T(n! * n*(n-1)!) = T((n!)²)

请问我的推导是否存在疏漏？

解答 #

你的推导确实存在疏漏，核心问题是重复计算了递归过程中的操作成本。我们可以通过递归式重新分析：

设T(k)为处理长度为k的数组的时间复杂度：

1. 基准情况：T(1) = O(1)，仅返回一个单元素数组，操作成本可忽略。

2. 递归情况（k>1）：
   外层循环执行k次，每次循环包含：

   • 数组交换、弹出：O(1)的常数操作
   • 递归调用T(k-1)，得到(k-1)!个排列
   • 遍历(k-1)!个排列并执行push操作：O((k-1)!)的时间
   • 用concat合并结果：O((k-1)!)的时间（等于被合并数组的长度）

   因此每次循环的时间是T(k-1) + O((k-1)!)，k次循环的总时间为：

   T(k) = k*T(k-1) + k*O((k-1)!) = k*T(k-1) + O(k!)
   

展开递归式验证：

• 代入T(k-1) = (k-1)*T(k-2) + O((k-1)!)，可得：
  T(k) = k*(k-1)*T(k-2) + 2*O(k!)
• 持续展开到基准情况T(1)=O(1)：
  T(k) = k!*T(1) + k*O(k!) = O(k!) + O(k*k!) = O(k*k!)

你之前的错误在于，错误地将递归树的每个节点都乘以了n*(n-1)!，但实际上各层级的操作成本是累加而非相乘的：

• 处理长度为n的数组时，总push操作量是n*(n-1)! = n!
• 处理长度为n-1的数组时，总push操作量是(n-1)*(n-2)! = (n-1)!
• 以此类推，所有层级的push操作总和为n! + (n-1)! + ... + 1! = O(n!)
• 再加上递归调用本身的开销，最终整体时间复杂度为O(n*n!)

另外，代码中results.concat(prems)的开销也已包含在上述分析中，不会额外提升复杂度量级。

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