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) ソリューションよりも時間の複雑さの点で価値があります。

編集:
正確には、 for each k-log(k!)が inであることを知っているため、 for each がinTheta(klogk)であることがk=2^nわかりますlg((2^n)!)Theta(2^nlog(2^n) = Theta(n*2^n)

于 2011-05-21T21:40:02.667 に答える
2

スターリングの式を適用すると、実際には O(n*2^n) になります。

于 2011-05-21T22:08:14.480 に答える
2

これは 2^n * $value であり、$value は 1 よりも大きく (すべての i > 2)、n に応じて増加します増加するので、明らかに定数ではありません。

于 2011-05-21T21:41:10.153 に答える