使用回溯的所有子集的时间复杂度

Question

我想了解使用回溯时的时间复杂度。问题是

Given a set of unique integers, return all possible subsets. Eg. Input [1,2,3] would return [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] I am solving it using backtracking as this:

private List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> getSubsets(int[] nums) {
    
    for (int length = 1; length <= nums.length; length++) { //O(n)
        backtrack(nums, 0, new ArrayList<>(), length);
    }
    result.add(new ArrayList<>());
    return result;
}

private void backtrack(int[] nums, int index, List<Integer> listSoFar, int length) {
    if (length == 0) {
        result.add(listSoFar);
        return;
    }
    
    for (int i = index; i < nums.length; i++) { // O(n)
        List<Integer> temp = new ArrayList<>(); 
        temp.addAll(listSoFar);                 // O(2^n)
        temp.add(nums[i]);
        backtrack(nums, i + 1, temp, length - 1);
    }
}

代码运行良好，但我无法理解 time/space 的复杂性。

我在想的是递归方法被调用了n次。在每次调用中，它都会生成最多包含 2^n 个元素的子列表。所以时间和 space 都是 O(n x 2^n)，对吗？

是吗？如果没有，谁能详细说说？

请注意，我在这里看到了一些答案，例如但无法理解。当递归出现时，我发现有点难以理解它。

Answer 1

您的代码运行效率不高。

与link中的第一个解决方案一样，您只考虑包含或不包含数字。（喜欢组合）

这意味着，您不必在 getSubsets 和 backtrack 函数中进行迭代。 “backtrack”函数可以使用参数

迭代“nums”数组

private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> getSubsets(int[] nums) {
    
    backtrack(nums, 0, new ArrayList<>(), new ArrayList<>());
    return result;
}

private void backtrack(int[] nums, int index, List<Integer> listSoFar) 
// This function time complexity 2^N, because will search all cases when the number included or not
{
    if (index == nums.length) {
        result.add(listSoFar);
        return;
    }
    
    // exclude num[index] in the subset 
    backtrack(nums, index+1, listSoFar)
    // include num[index] in the subset
    backtrack(nums, index+1, listSoFar.add(nums[index]))
}

Answer 2

您对 space 复杂性的看法完全正确。最终输出的总 space 是 O(n*2^n)，这占程序使用的总 space 的主导。不过，时间复杂度的分析略有偏差。最佳情况下，在这种情况下，时间复杂度与 space 复杂度相同，但这里存在一些低效率（其中之一是您实际上并没有回溯），因此时间复杂度实际上是 O (n^2*2^n) 最多。

根据调用递归方法的次数乘以每次调用的工作量来分析递归算法的时间复杂度绝对有用。但是要小心说 backtrack 只被调用 n 次：它在顶层被调用 n 次，但这忽略了所有后续的递归调用。此外，顶层的每个调用 backtrack(nums, 0, new ArrayList<>(), length); 负责生成所有大小为 length 的子集，其中有 n Choose length。也就是说，没有任何一个顶级调用会产生 2^n 个子集；相反，对于从 0 到 n 的长度，n Choose length 的总和是 2^n:

知道在所有递归调用中，您会生成 2^n 个子集，然后您可能想询问在生成每个子集时完成了多少工作以确定整体复杂性。最佳情况下，这将是 O(n)，因为每个子集的长度从 0 到 n 不等，平均长度为 n/2，因此整个算法可能是 O(n/2*2^n) = O(n*2^n)，但您不能假设子集是最佳生成的并且没有完成任何重要的额外工作。

在您的例子中，您正在通过 listSoFar 变量构建子集，直到它达到适当的长度，此时它被附加到结果中。但是，listSoFar 会在 O(n) 时间内将其每个 O(n) 个字符复制到临时列表中，因此生成每个子集的复杂度为 O(n^2)，这使整体复杂度为O(n^2*2^n)。此外，创建了一些 listSoFar 子集，这些子集永远不会计入最终输出（您永远不会检查 nums 中是否还有足够的数字来填充 listSoFar 到所需的 length 在递归之前），所以你最终在构建子集和进行递归调用方面做了不必要的工作，这些工作永远不会到达基本情况以附加到 result，这也可能会恶化渐近复杂性。您可以通过回溯解决第一个低效率问题，然后使用简单的 break 语句解决第二个问题。我将这些更改写入 JavaScript 程序，大部分逻辑保持不变，但 re-naming/re-organizing 一点点：

function getSubsets(nums) {
  let subsets = [];
  for (let length = 0; length <= nums.length; length++) {
    // refactored "backtrack" function:
    genSubsetsByLength(length); // O(length*(n Choose length))
  }
  return subsets;

  function genSubsetsByLength(length, i=0, partialSubset=[]) { 
    if (length === 0) {
      subsets.push(partialSubset.slice()); // O(n): copy partial and push to result
      return;
    }
    while (i < nums.length) {
      if (nums.length - i < length) break; // don't build partial results that can't finish
      partialSubset.push(nums[i]); // O(1)
      genSubsetsByLength(length - 1, ++i, partialSubset);
      partialSubset.pop(); // O(1): this is the back-tracking part
    }
  }
}
for (let subset of getSubsets([1, 2, 3])) console.log(`[`, ...subset, ']');

关键区别在于使用回溯来避免每次向其中添加新元素时都复制部分子集，这样每个元素都是在 O(length) = O(n) 时间内构建的，而不是 O (n^2) 次，因为现在每个添加的元素仅完成 O(1) 次工作。在每次递归调用后弹出添加到部分结果的最后一个字符允许您在递归调用中重复使用相同的数组，从而避免为每次调用制作 temp 副本的 O(n) 开销。这一点以及仅构建出现在最终输出中的子集这一事实允许您根据输出中所有子集的元素总数来分析总时间复杂度：O(n*2^n)。

使用回溯的所有子集的时间复杂度

Time complexity for all subsets using backtracking

java

subset

backtracking