数组排列递归算法的时间/空间复杂度分析求助

问题描述 #

我编写了一段生成数组排列的递归代码，现需分析其Time/Space复杂度。已知代码使用Array.forEach方法包含O(n)复杂度，但不清楚递归对整体时间复杂度的影响。我认为递归本身是O(n)复杂度，那整体是否为O(n²)？另外，因每次递归调用返回更大的内存数组，空间复杂度是否为O(n)？恳请解答。

代码实现 #

function getPermutations(array) {
    if (array.length <= 1){
      return array.length === 0 ? array : [array];
    }
    
    let lastNum = array[array.length - 1]
    let arrayWithoutLastNum = array.slice(0, array.length - 1); 
    let permutations = getPermutations(arrayWithoutLastNum);
  
    let memory = []
    permutations.forEach(element => {
      for(let i = 0; i <= element.length; i++){
        let elementCopy = element.slice(0);
        elementCopy.splice(i, 0, lastNum)
        memory.push(elementCopy)
      }
    })
  
    return memory
}

时间复杂度分析 #

你的初始判断有误，整体时间复杂度并非O(n²)，而是O(n × n!)，原因如下：

• 生成n个元素的排列总数是n!，这是排列问题的固有规模。
• 递归每一层的处理逻辑：当处理k个元素的排列时，我们会把第k+1个元素插入到每个k长度排列的k+1个位置中。每个插入操作包含slice（复制数组，O(k)时间）和splice（插入元素，O(k)时间），单个插入的时间成本是O(k)。
• 递归过程的时间总和为：1!×1 + 2!×2 + 3!×3 + ... + n!×n，这个求和式的结果等于(n+1)! - 1，其主导项为n×n!，因此整体时间复杂度是O(n×n!)。

空间复杂度分析 #

空间复杂度也并非O(n)，而是O(n × n!)，主要来自两部分：

1. 递归调用栈：递归深度等于数组长度n，这部分空间是O(n)，属于次要项。
2. 存储排列的内存：最终需要存储n!个长度为n的排列，每个排列占用O(n)空间，这部分总空间是O(n×n!)，是主导项。
   另外，递归过程中每一层的临时数组（比如memory）会在当前层递归结束后返回给上层，不会额外累积过多空间，但最终的排列集合是空间占用的主要来源。

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