algorithm - 理解大 O 的幂集

Question

我写了一个幂集算法，写成 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 where c > 1)，因为我在枚举所有可能的子集.

Answer 1

外循环运行的次数是a.length。内部循环运行的次数为pw.length，但随着函数的运行而增加。所以你不能说他们都是O(n)。此外，pw.addAll(tmp)不是恒定时间。

这里，渐近时间复杂度与调用的次数相同tmp.add()，等于pw:的最终大小O(2^n)。