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 加到上述等式的每一边并化简:

对上述等式两边取 log，并使用 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)转换为二进制形式 here ，正如@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 变大，快速接近统一: