递归幂集函数的时间复杂度

Question

我在简化用于查找给定输入集的幂集的递归算法的时间复杂度时遇到了问题。到目前为止，我也不完全确定我得到的是否正确。

在这个 link 的页面底部有描述：http://www.ecst.csuchico.edu/~akeuneke/foo/csci356/notes/ch1/solutions/recursionSol.html

通过考虑函数为任意选择的大小为 4 的输入集采取的每个步骤，然后将其转换为大小为 n 的输入集，我得出的结果是大 O 表示法的时间复杂度对于这个算法是：2ⁿnⁿ

这是正确的吗？是否有一种特定的方法来计算递归函数的时间复杂度？

Answer 1

的运行-时间实际上是O(n*2ⁿ)。简单的解释是，这是一个渐进最优算法，因为它所做的总工作主要是创建直接在算法最终输出中具有特征的子集，生成的输出的总长度为 O(n*2ⁿ)。我们还可以分析伪代码的注释实现（在 JavaScript 中）以更严格地显示这种复杂性：

function powerSet(S) {
  if (S.length == 0) return [[]]  // O(1)
  let e = S.pop()                 // O(1)
  let pSetWithoutE = powerSet(S); // T(n-1)
  let pSet = pSetWithoutE         // O(1)
  pSet.push(...pSetWithoutE.map(set => set.concat(e))) // O(2*|T(n-1)| + ||T(n-1)||)
  return pSet; // O(1)
}
// print example:
console.log('{');
for (let subset of powerSet([1,2,3])) console.log(`\t{`, subset.join(', '), `}`);
console.log('}')

其中T(n-1)表示对n-1个元素进行递归调用的运行次，|T(n-1)|表示递归调用返回的幂集中子集的个数, ||T(n-1)|| 表示递归调用返回的所有子集中的元素总数。

用这些术语表示的具有复杂性的线对应于伪代码步骤 2. 的第二个要点：返回没有元素 e 的幂集的并集，以及具有每个元素的相同幂集子集 s 与 e 合并：

(1) U ((2) = {s in (1) U e})

这个联合是在推送和连接操作方面实现的。 push 在 |T(n-1)| 时间内将 (1) 与 (2) 合并，因为 |T(n-1)| 新子集正在合并到幂集中。 concat 操作的映射负责通过在 |T(n-1)| + ||T(n-1)|| 时间内将 e 附加到 pSetWithoutE 的每个元素来生成 (2)。第二个复杂度对应于 pSetWithoutE 的 |T(n-1)| 个子集中有 ||T(n-1)|| 个元素（根据定义），并且每个子集的大小都增加了 1。

然后我们可以将输入大小 n 上的运行时间表示为：

T(n) = T(n-1) + 2|T(n-1)| + ||T(n-1)|| + 1; T(0) = 1

通过归纳可以证明：

|T(n)| = 2<sup>n</sup> 
||T(n)|| = n2<sup>n-1</sup>

产生：

T(n) = T(n-1) + 2*2<sup>n-1</sup> + (n-1)2<sup>n-2</sup> + 1; T(0) = 1

当你解析地解决这个递归关系时，你得到：

T(n) = n + 2<sup>n</sup> + n/2*2<sup>n</sup> = O(n2<sup>n</sup>)

这与最佳幂集生成算法的预期复杂度相匹配。递归关系的解也可以直观的理解：

n 次迭代中的每一次迭代都在生成幂集的新子集之外工作 O(1)，因此最终表达式中的 n 项。

就生成幂集的每个子集所做的工作而言，每个子集在通过concat生成后被推送一次。有 2ⁿ 个子集被压入，产生 2ⁿ 项。每个子集的平均长度为 n/2，给出的组合长度为 n/2*2ⁿ，这对应于所有连接操作的复杂性。因此，总时间为 n + 2ⁿ + n/2*2ⁿ.

递归幂集函数的时间复杂度

Time Complexity of recursive Power Set function

recursion

time-complexity

big-o

powerset