0

P(a) と書かれたべき集合のアルゴリズムを書きました。アルゴリズム (Big-O) の時間の複雑さについて学んでいるので、間違っている場合は修正してください。

アルゴリズム：

function powerSet(int[] a ){
ArrayList pw = new ArrayList();
pw.add(" ");
for (int i = 1; i <= a.length; i++) //O(n){
            ArrayList<String> tmp = new ArrayList<String>();

            for (String e : pw)//O(n) {
                if(e.equals(" "))
                    tmp.add(""+a[i-1]) //contanst time;
                else
                    tmp.add(e+a[i-1]) //constant time;
            }
            pw.addAll(tmp)//O(1);
        }
        return pw;
}

この O(n)*O(n) = O(n^2) の時間計算量ですか、または 2^n のような指数関数 (c^n c > 1) です。これは、すべての可能なサブセットを列挙しているためです。 .

4

1 に答える 1

1

外側のループの実行回数は ですa.length。内側のループが実行される回数は ですがpw.length、これは関数が実行されるにつれて増加します。だから両方とも言えないO(n)。また、pw.addAll(tmp)一定時間ではありません。

ここで、漸近的な時間計算量は呼び出される回数と同じで、 :tmp.add()の最終的なサイズに等しくなりpwますO(2^n)。

于 2012-12-27T07:32:11.870 に答える