这是什么幂算法的运行时间

我有一个算法使用的所有位的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）的时间（不占空间）递归地解决，所以我不知道上面的方法比这更好还是更差，因为它在空间上更好。

来源

2011-05-21 Aly

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-21 21:40:02 amit

为什么是x！ > 2^x，仍然投票，但将非常感激，如果你可以解释:) – Aly 2011-05-21 21:46:30

@Aly：因为X！ = 1 * 2 * 3 ... * x（x次，其中除了第一个和第二个元素都大于2）其中2^x = 2 * 2 * ... * 2（x次，其中全部为2 ... ）所以对于大的x，x！> 2^x – amit 2011-05-21 21:48:19

非常感谢！ – Aly 2011-05-21 23:09:51

没有试图解决或模拟，很容易看出这比O（2^n）更差，因为这是2^n * $值，其中$ value大于1（对于所有i> 2）并且随着n增加而增加，所以显然不是一个常数。

来源

2011-05-21 21:41:10

应用Sterling公式，它实际上是O（n * 2^n）。

来源

2011-05-21 22:08:14

这是什么幂算法的运行时间

回答

相关问题