這是什麼冪算法的運行時間

我有一個算法使用的所有位的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

這是什麼冪算法的運行時間

回答

相關問題