该子算法的空间复杂度实际上是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 n）_时间复杂度和 _O（2 n）_空间复杂度运行。我同意她的观点，该算法运行时间为 _O（2
n），_因为要解决此问题，您必须考虑以下事实：对于任何元素，您都有两种可能性，它可以在集合中或不在集合中。并且因为您有n个元素，所以您的问题将有2
n个可能性，因此可以用O（2 n）时间解决问题。

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

我有一个示例正在生成[1,2,3]作为[1,2,3]的子集。这是要生成的递归调用集set
generateSubsets（[]，subsets，[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 n ）。