math - 为什么 powerset 给出 2^N 的时间复杂度？

Question

下面是生成powerset的递归函数

void powerset(int[] items, int s, Stack<Integer> res) {
     System.out.println(res);

     for(int i = s; i < items.length; i++) {
          res.push(items[i]);
          powerset(items, s+1, res);
          res.pop();
     }
}

我真的不明白为什么这会花费 O(2^N)。 2 来自哪里？为什么 T(N) = T(N-1) + T(N-2) + T(N-3) + .... + T(1) + T(0) 解决了O(2^n)。有人可以解释为什么吗？

Answer 1

每次我们决定向原始数组添加另一个元素时，我们都会将操作次数加倍。

例如，假设我们只有空集 {}。如果我们想添加 {a}，幂集会发生什么变化？然后我们将有 2 个集合:{}、{a}。如果我们想添加 {b} 怎么办？我们将有 4 个集合:{}、{a}、{b}、{ab}。

注意 2^n 也暗示了双重性质。2^1 = 2, 2^2 = 4, 2^3 = 8, ...