我有一个算法可以使用 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) 时间(而不是空间)递归地解决,所以我想知道上面的方法是否比这更好或更差,时间上为在太空中更好。