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)。