编程面试要素 - 16.4 生成幂集 - 解决 1 次复杂度问题

Question

希望你们一切都好。

我有一个关于 Adnan 和 Tsung-Hsien 所著《编程面试要素》一书中问题 16.4 - 生成幂集的解决方案 1 的时间复杂度的问题。

该问题指示读者“编写一个函数，将一个集合作为输入并返回其幂集”。输入是集合 S = {0,1,2}。

我明白最多有 2^n 方法的递归调用 directedSoFar. 。然而我不明白我们为什么要花钱 O(n) 一次通话内的时间 directedSoFar. 。该方法内部没有循环，在递归情况下只有 2 行用于向当前添加和删除元素 selectedSoFar 解决方案，以及基本情况下的另外 2 行。这是否意味着我们只在通话中花费恒定的时间，而不是 O(n) 时间？

我为此苦恼了一段时间，并在官方论坛和 Reddit 上发帖，但没有得到回应。如果有人愿意慷慨地帮助我，我将不胜感激。

谢谢

Answer 1

请注意以下代码行：

powerSet.add(new ArrayList<>(SelectedSoFar);

每当我们创建一个子集时，我们都会将该子集（列表）添加到 list 的列表中： power set. 。子集的大小将是 $n$ （实际上它会有所不同 $1$ 到 $n$, ，但我们可以将其视为 $n$).

即使添加列表需要 一行代码, ，但这将涉及复制所有元素。这就是为什么需要 O(n) 时间。