迭代生成给定数组所有子集的时间与空间复杂度分析

代码回顾 #

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> subsets = new ArrayList();
    subsets.add(new ArrayList());
    int pos = 0;
    while(pos < nums.length){
        int currentSize = subsets.size();
        for(int i = 0; i < currentSize; i++){
            List<Integer> copy = new ArrayList(subsets.get(i));
            copy.add(nums[pos]);
            subsets.add(copy);
        }
        pos++;
    }
    return subsets;
}

时间复杂度分析 #

你说子集总数是2^N没错，但代码的耗时不能只看子集的数量——生成每个子集时需要复制已有子集的元素，这部分操作的开销必须算进去。

具体拆解：

• 处理数组中第k个元素时，需要复制当前已有的2^k个子集，每个子集的复制时间等于该子集的元素个数。
• 把所有复制操作的总工作量加起来，本质是计算所有子集的元素总数之和。对于每个元素，它会出现在2^{(N-1)个子集里（剩下的N-1个元素可选可不选），因此总元素数为N*2}(N-1)。
• 最终时间复杂度为 **O(N*2^{N)**，这就是耗时比单纯2}N高的原因：我们不是只统计子集数量，而是要实际构建每个子集的元素集合，这涉及大量的元素复制操作。

空间复杂度分析 #

空间复杂度由最终存储的所有子集的元素总数决定：

• 最终要存储2^{N个子集，总元素数是N*2}(N-1)，每个元素都占用内存空间。
• 因此空间复杂度也是 O(N*2^N)。

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