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

Question

这是 Cracking the Coding Interview 5^th
中的第 9.4 题 问题： 编写一个方法 return 一个集合的所有子集。

这是我在 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ⁿ) space 复杂度。我同意她的看法，这个算法在 O(2ⁿ) 时间内运行，因为要解决这个问题，你必须考虑这样一个事实元素，你有两种可能性，它可以在集合中，也可以不在集合中。因为你有 n 个元素，你的问题将有 2ⁿ 种可能性，所以问题将用 O(2ⁿ) 时间解决。

但是我相信我有一个令人信服的论点，即我的算法在 O(n) space 中运行。我知道 space 复杂度是 "the total space taken by an algorithm with respect to the input size" Space Complexity 并且与递归调用的深度相关（记得我看过的一些 Youtube 视频）

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

这表明递归调用相对于原始集合大小n的最大深度是n本身。这些递归调用中的每一个都有自己的堆栈框架。因此，据此，我得出结论 space 复杂度为 O(n) 有人看到我的证明中有什么缺陷吗？

Answer 1

您需要考虑您的算法分配的所有内存（或者更确切地说，任何时候分配的最大内存量 "in use"）——不仅在堆栈上，而且在堆上。每个生成的子集都存储在 subsets 列表中，该列表最终将包含 2ⁿ 集合，每个集合的大小介于0 和 n（大多数集合包含大约 n / 2 个元素）- 所以 space 复杂度实际上是 O(n 2ⁿ).

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

Is the space complexity of this subset algorithm actually O(n)?

java

algorithm

recursion

time-complexity

space-complexity