枚举子集的 space 复杂度是多少？

Question

这是基于我对 space 复杂性提出的其他问题。

这是我枚举（命名）所有集合问题的解决方案。（测试过，有效）

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ⁿ 个子集。这是评估该算法时间复杂度的可接受方法吗（找不到递归关系来执行此操作）？

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

我想在这里应用同样的方法。假设我的测试集是 {1,2,3}。为了生成子集{1,2,3}，从我的算法中，当最终打印出{1,2,3}时，这些"subsets"也存在于内存中， - {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);
    }

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

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

Answer 2

你可以用双变量递归关系来解决这个问题。方法调用的时间复杂度取决于 s 的大小和散列集的大小（我们称之为 h）。那么：

T(s, h) = O( h               //First loop
             + s - 1)         //Second loop 
           + T(s - 1, h + 1) //First recursive call
           + T(s - 1, h)     //Second recursive call
T(0, h) = O(1)

我们对 T(n, 0) 感兴趣。 space 复杂度除了 S(0, h) = 0 之外，同样的递推关系成立。这假设创建的集合永远不会被销毁。

T(s, ...) 的每个实例都会生成两个 T(s - 1, ...) 实例。我们从 T(n, ...) 开始，以 T(0, ...)=O(1) 的 2^n 个实例结束。所以

T(n, 0) = 2^n * O(1) + ...

此外，我们必须考虑生成的 hs 和 s-1s。让我们从 s-1 开始。第一次展开后，会有1n-1。在第二次扩展之后，将有另外两个 n-2。在第三次扩展之后，将执行额外的 4 n-3... 和 n 扩展来生成这些项。总计：Sum {i from 1 to n} (2^(i-1)*(n-i)) = 2^n - n - 1。所以：

T(n, 0) = 2^n * O(1) + O(2^n - n - 1) + ...

最后，h 条款。这有点棘手。第一次展开只会导致零项。下一个扩展会产生一个 1 和一个 0 项。然后一个2，两个1，一个0。该数字始终等于二项式系数：Sum { e from 0 to n-1 } (Sum { i from 0 to e } ( i * Binom(e, i) )) = 1 - (n-1)*2^n。所以最后：

T(n, 0) = 2^n * O(1) + O(2^n - n - 1) + O(1 - (n-1)*2^n)
        = O(n*2^n)

如果保留所有创建的集，则同样的复杂性适用于 space 要求。

枚举子集的 space 复杂度是多少？

What is the space complexity of enumerating subsets?

java

algorithm

recursion

time-complexity

space-complexity