这段代码的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

假设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 2

---

时间复杂性：

这里有一种推导时间复杂度的替代方法（与@templatetypedef相比）

设M为代码中的总步骤数。外for循环运行2次^N次次，内for循环运行log（i）次，因此我们有：

将2提升到上述等式的每一侧，并简化：

取上述方程两边的log，并使用斯特林近似（log（x！）~xLog（x）-x）

---

位操作：

为了解决你在比特操作方面的弱点，你实际上并不需要它。它在代码中有三种使用方式，所有这些都可以用模糊程度较低的函数替换：

1. 2的力量：（^{）→ （Math.pow(2, array.length)）
2. 除以2:（^{）→ （x /= 2）
3. 模量2：(x & 1)→ (x % 2)

---

代码解释：

此外，为了解决代码所做的事情，它本质上是使用here所示的方法将每个数字（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ⁿ！）在sterling近似中，当n变大时，你可以看到它很快接近单位：