java - 此代码列出集合的所有子集的时间复杂度？

Question

我在网上找到了许多具有 O(2^n) 复杂性的解决方案。有人可以帮我弄清楚下面给出的代码的时间复杂度。它还涉及很多位操作，我在这方面真的很弱，所以我不太了解代码的窍门。如果有人可以解释代码，那就太好了。

private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
  {
    int pos = array.length - 1;
    int bitmask = i;

    System.out.print("{");
    while(bitmask > 0)
    {
      if((bitmask & 1) == 1)
         System.out.print(array[pos]+",");
     {
        bitmask >>= 1;
        pos--;
     }
     System.out.print("}");
  }
}

这是最优化的解决方案吗？

Answer 1

---

时间复杂度：

这是导出时间复杂度的另一种方法（与@templatetypedef 相比）。

令M为代码中的总步数。您的外部 for 循环运行2 ^N次，内部循环运行log(i)次，因此我们有：

将2提高到上述等式的每一边并简化：

取上述等式两边的对数，并使用 Sterlings Approximation ( Log (x!) ~ xLog(x) - x )

---

位操作：

为了解决您在位操作方面的弱点，您实际上并不需要它。它在您的代码中以三种方式使用，所有这些都可以用较少混淆的函数替换：

1. 2 的幂：( ) 1 << array.length→ ( Math.pow(2, array.length))
2. 除以 2： ( x >>= 1) → ( x /= 2)
3. 模数 2： (x & 1) →(x % 2)

---

代码说明：

此外，为了解决代码在做什么，它本质上是使用此处显示的方法将每个数字（0 到 2 ^N）转换为二进制形式，并且正如@templatetypedef 所述，1 表示对应的元素在集合中。这是使用此方法将 156 转换为二进制的示例：

作为您的代码的示例：

pos = array.length - 1;
bitmask = 156;                              // as an example, take bitmask = 156
while(bitmask > 0){
    if(bitmask%2 == 1)                      // odd == remainder 1, it is in the set
         System.out.print(array[pos]+",");
    bitmask /= 2;                           // divide by 2
    pos--;
}

通过对所有位掩码（0 到 2 ^N）执行此操作，您将找到所有唯一可能的集合。

---

编辑：

下面看一下英镑近似中的比率 (n2 ⁿ /log ₂ (2 ⁿ !)，您可以看到它随着 n 变大而迅速接近统一：

Answer 2

此代码通过使用恰好具有 n 位的二进制数和一组 n 个元素的子集之间的连接来工作。如果您将集合的每个元素分配给一个位并将“1”视为“将元素包含在子集中”，将“0”视为“将元素从子集中排除”，那么您可以轻松地在两者之间进行转换. 例如，如果该集合包含 a、b 和 c，则 100 可能对应于子集 a，011 对应于子集 bc，等等。尝试用这种洞察力再次阅读代码。

在效率方面，上述代码在实践和理论上都非常快。任何列出子集的代码都必须花费大量时间来列出这些子集。所需时间与必须列出的元素总数成正比。此代码为列出的每个项目花费 O(1) 工作，因此是渐近最优的（当然，假设没有太多元素会溢出正在使用的整数）。

此代码的总复杂度可以通过计算打印的总元素数来确定。我们可以计算出一些数学来解决这个问题。请注意，有 n 个选择 0 个大小为 0 的子集，n 个选择 1 个大小为 1 的子集，n 个选择了 2 个大小为 2 的子集，依此类推。因此，打印的元素总数由下式给出

C = 0 × (n 选择 0) + 1 × (n 选择 1) + 2 × (n 选择 2) + … + n × (n 选择 n)

注意 (n 选择 k) = (n 选择 n - k)。所以：

C = 0 × (n 选择 n) + 1 × (n 选择 n - 1) + 2 × (n 选择 n - 2) + … + n × (n 选择 0)

如果我们把这两个加在一起，我们得到

2C = n × (n 选择 0) + n × (n 选择 1) + … + n × (n 选择 n)

      = n × (n 选择 0 + n 选择 1 + … + n 选择 n)

二项式定理说带括号的表达式是 2 ⁿ，所以

2C = n2 ⁿ

所以

C = n2 ^n-1

所以恰好打印了 n2 ^{n-1 个}元素，所以这种方法的时间复杂度是 Θ(n 2 ⁿ )。

希望这可以帮助！

Answer 3

让我们说array.length是n。此代码的工作原理是根据从 0 到 2^n 的所有数字的二进制表示从集合中选择或排除元素，这些数字恰好是集合的所有组合。

对于外部 for 循环，您的复杂度是 O(2^n)，因为numOfSubsets = 1 << array.length 它是 2^n。对于内部循环，您正在向右移动，最坏的情况是 111...1（n 位设置为 1），因此在最坏的情况下您将获得 O(n) 复杂度。所以总复杂度将是 O(n*(2^n))。

Answer 4

https://github.com/yaojingguo/subsets给出了解决子集问题的两种算法。Iter算法与问题中给出的代码相同。Recur算法使用递归来访问每个可能的子集。两种算法的时间复杂度都是Θ(n*2^n)。在Iter算法中，1语句执行n*2^n次数。2语句执行n*2^(n-1)（基于@templatetypedef 的分析）。用于a表示 的成本1。并b用来表示成本2。总成本为n*2^n*a + n*2^(n-1)*b。

if ((i & (1 << j)) > 0) // 1
    list.add(A[j]); // 2

下面是Recur算法的主要逻辑：

result.add(new ArrayList<Integer>(list)); // 3
for (int i = pos; i < num.length; i++) { // 4
  list.add(num[i]);
  dfs(result, list, num, i + 1);
  list.remove(list.size() - 1);
}

语句3的成本n*2^(n-1)*b与1. 另一个成本是4循环。每个循环迭代包括三个函数调用。4总共执行2^n次数。用于d表示 的成本4。总成本为2^n*d + n*2^(n-1)*b。下图是该算法的递归树 set {1, 2, 3, 4}。更精确的分析需要以2^(n-1)不同方式处理叶节点。

Ø --- 1 --- 2 --- 3 --- 4 | | |- 4 | |- 3 --- 4 | |- 4 |- 2 --- 3 --- 4 | |- 4 |- 3 --- 4 |- 4

比较这两种算法的复杂度就是比较n*2^n*a（1）和2^n*d（2）。将 (1) 除以 (2)，我们有n * a / d。如果n*a小于d，Iter则比 快Recur。我用来Driver对这两种算法的效率进行基准测试。这是一次运行的结果：

n: 16
Iter mills: 40
Recur mills: 19
n: 17
Iter mills: 78
Recur mills: 32
n: 18
Iter mills: 112
Recur mills: 10
n: 19
Iter mills: 156
Recur mills: 149
n: 20
Iter mills: 563
Recur mills: 164
n: 21
Iter mills: 2423
Recur mills: 1149
n: 22
Iter mills: 7402
Recur mills: 2211

它表明，对于小n，Recur比Iter。