这个子集算法的空间复杂度实际上是 O(n) 吗？

Question

这是破解编码面试5问题9.4^次
的问题：写返回一组的所有子集的方法。

这是我在 Java 中的解决方案。（测试它，它有效！！！）

public static List<Set<Integer>> subsets(Set<Integer> s) {
    Queue<Integer> copyToProtectData  = new LinkedList<Integer>();
    for(int member: s) {
        copyToProtectData.add(member);
    }
    List<Set<Integer>> subsets = new ArrayList<Set<Integer>>();
    generateSubsets(copyToProtectData, subsets, new HashSet<Integer>());
    return subsets;
}
private static void generateSubsets(Queue<Integer> s, 
        List<Set<Integer>> subsets, Set<Integer> hashSet) {
    if(s.isEmpty()) {
        subsets.add(hashSet);
    } else {
        int member = s.remove();
        Set<Integer> copy = new HashSet<Integer>();
        for(int i:hashSet) {
            copy.add(i);
        }
        hashSet.add(member);
        Queue<Integer> queueCopy = new LinkedList<Integer>();
        for(int i:s){
            queueCopy.add(i);
        }
        generateSubsets(s, subsets, hashSet);
        generateSubsets(queueCopy, subsets, copy);          
    }
}

我查看了这个问题的解决方案，作者说这个算法的解决方案在O(2 ⁿ )时间复杂度和O(2 ⁿ )空间复杂度中运行。我同意她的观点，该算法在O(2 ⁿ )时间内运行，因为要解决这个问题，您必须考虑这样一个事实，即对于任何元素，您都有两种可能性，它可以在集合中，也可以不在集合中。并且因为您有 n 个元素，您的问题将有 2 ^{n 种}可能性，因此该问题将在 O(2 ⁿ ) 时间内解决。

但是，我相信我有一个令人信服的论点，即我的算法在O(n)空间中运行。我知道空间复杂度是“算法相对于输入大小占用的总空间” 空间复杂度，并且与递归调用的深度有关（从我观看的一些 Youtube 视频中记住这一点）

我的一个例子是将 [1,2,3] 生成为 [1,2,3] 的子集。这是一组递归调用以生成该集合
generateSubsets([], subnets, [1,2,3])
generateSubsets([3],subsets,[1,2])
generateSubsets([2,3],subsets, [1])
generateSubsets([1,2,3],subsets,[])

这表明递归调用相对于原始集合大小 n 的最大深度是 n 本身。这些递归调用中的每一个都有自己的堆栈帧。所以从这里，我得出结论，空间复杂度是O(n)有没有人看到我的证明中有任何缺陷？

Answer 1

您需要考虑由您的算法分配的所有内存（或者更确切地说，在任何时候“使用中”的最大分配内存量）——不仅在堆栈上，而且在堆上。每个生成的子集都存储在subsets列表中，最终将包含 2 ^{n 个}集合，每个集合的大小介于 0 和n之间（大多数集合包含大约n / 2 个元素）-因此空间复杂度实际上是O（n 2 ⁿ )。