列出该集的所有子集的时间复杂度？

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

该代码通过使用具有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 2

时间复杂性:

以下是导出时间复杂度的另一种方法(与@templatetypedef相比).

设M是代码中的步骤总数.你的外部for循环运行2 ^N次,内部运行log(i)次,所以我们有:

向上面的等式的每一边提高2并简化:

就拿日志上面的等式的两边,并且使用STERLING公司逼近(日志(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变大而快速逼近统一: