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

Question

这是问题 9.4 从 破解编码访谈 5^th
问题： 编写一个方法来返回集合的所有子集。

这是我在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ⁿ可能性，所以问题将在O（2ⁿ）时间内解决。

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

我的一个例子是生成[1，2，3]作为[1，2，3]的子集。以下是用于生成该集合的递归调用集< br> 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

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