5

我有一个算法可以使用 0 到 2^n 之间的所有位来计算集合的幂集：

public static <T> void findPowerSetsBitwise(Set<T> set, Set<Set<T>> results){
        T[] arr = (T[]) set.toArray();
        int length = arr.length;

        for(int i = 0; i < 1<<length; i++){
            int k = i;
            Set<T> newSubset = new HashSet<T>();
            int index = arr.length - 1;
            while(k > 0){
                if((k & 1) == 1){
                    newSubset.add(arr[index]);
                }
                k>>=1;
                index --;
            }
            results.add(newSubset);
        }

    }

我的问题是：这个算法的运行时间是多少。该循环运行 2^n 次，并且在每次迭代中，while 循环运行 lg(i) 次。所以我认为运行时间是

T(n) = the sum from i=0 to i=2^n of lg(i)

但我不知道如何进一步简化，我知道这可以在 O(2^n) 时间（而不是空间）递归地解决，所以我想知道上面的方法是否比这更好或更差，时间上为在太空中更好。

4

3 回答 3

6 
sigma(lg(i)) where i in (1,2^n) 
= lg(1) + lg(2) + ... + lg(2^n)     
= lg(1*2*...*2^n) 
= lg((2^n)!) 
> lg(2^2^n) 
  = 2^n

因此，建议的解决方案在时间复杂度方面是值得的，然后是递归 O(2^n) 一个。

编辑：
确切地说，我们知道对于每个k-log(k!)都在Theta(klogk)，因此k=2^n我们得到lg((2^n)!)了Theta(2^nlog(2^n) = Theta(n*2^n)

于 2011-05-21T21:40:02.667 回答
2

在不尝试求解或模拟的情况下，很容易看出这比 O(2^n) 更糟，因为这是 2^n * $value 其中 $value 大于一（对于所有 i > 2）并且随着 n 的增加而增加增加，所以它显然不是一个常数。

于 2011-05-21T21:41:10.153 回答
2

应用 Sterling 公式，实际上是 O(n*2^n)。

于 2011-05-21T22:08:14.480 回答