java - 枚举子集的空间复杂度是多少？

Question

这是基于我对空间复杂性的其他问题。 Permutation Space Complexity

这是我枚举(命名)所有集合的问题的解决方案。 (测试了一下，可以)

public static void subsets(Set<Integer> s) {
    Queue<Integer> copyToProtectData  = new LinkedList<Integer>();
    for(int member: s) {
        copyToProtectData.add(member);
    }
    generateSubsets(copyToProtectData, new HashSet<Integer>());
}
private static void generateSubsets(Queue<Integer> s, 
         Set<Integer> hashSet) {
    if(s.isEmpty()) {
        System.out.println(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, hashSet);
        generateSubsets(queueCopy, copy);           
    }
}

我知道我的算法的时间复杂度是 O(2ⁿ) 因为离散数学中的一个解是集合 n 有 2ⁿ 子集。这是评估该算法时间复杂度的可接受方法吗(找不到递归关系来执行此操作)？

继续前进，我仍然难以评估空间复杂度。我正在尝试应用我从上一个问题中学到的知识。在我关于字符串排列的最后一个问题中，@ajb 说由于我存储了一个在每次递归调用时增长 1 的本地字符串，所以我的空间复杂度实际上是 O(n² )。

我正在尝试在此处应用相同的内容。假设我的测试集是 {1,2,3}。要生成子集 {1,2,3}，从我的算法中，当最终打印 {1,2,3} 时，这些“子集”也存在于内存中，- {1}，{}，{1,2} ,{1],{1,2,3}, {1,2}，这意味着它不仅仅是一个像排列问题中那样少了一个元素的子集。我还在每一轮都制作了剩菜的副本，这样一侧的操作就不会影响另一侧的副本。这就是为什么我不确定@ajb 的策略是否适用于此的原因。运行时仍然是 O(n²) 还是会更大？

Answer 1

通常情况下，如果您想要一个好的边界，您分析复杂性的方法是通过混合 amortized analysis和其他方法 - 例如，您可以尝试以迭代形式重写递归以便于分析。

更直接地回答您的问题:您的运行时间不是 O(2^n)。

代码的这些部分会将复杂度增加到 O(n*2^n)

    for(int i:hashSet) {
        copy.add(i);
    }

    for(int i:s){
        queueCopy.add(i);
    }

原因是您不仅要遍历每个子集，而且要遍历每个子集的每个元素。

关于您的空间复杂度问题，假设垃圾收集是最重要的，那么空间复杂度是 O(n^2)。即使你正在复制 2 个东西而不是 1 个，复杂度仍然是 O(n^2) 因为它只影响常数因子。如果您真的想保存所有子集的列表，那么空间复杂度就会一直上升到 O(n*2^n) - 不管怎样，您当前的输出仍然需要它。