子集问题迭代版时间复杂度疑问：O(N2^N)还是O(N2^(N-1))？

import java.util.ArrayList;
import java.util.List;

public class SubSet {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        List<List<Integer>> ans = subset(arr);
        for(List<Integer> list: ans)
        {
            System.out.println(list);
        }

    }

    static List<List<Integer>> subset(int[] arr)
    {
        List<List<Integer>> outer = new ArrayList<>();

        outer.add(new ArrayList<>());

        for(int num: arr)
        {
            int size = outer.size();
            for (int i = 0; i < size; i++)
            {
                List<Integer> internal = new ArrayList<>(outer.get(i));
                internal.add(num);
                outer.add(internal);
            }
        }

        return outer;
    }
}

我的老师称这段代码的时间复杂度为O(N2^{N)，但我认为应该是O(N2}(N-1))——因为处理第3个元素时内层循环运行4次，处理第4个元素时运行8次。我对时间复杂度的理解可能有误，恳请帮忙解惑。

为什么两种时间复杂度表述都正确 #

你的计算逻辑没问题，但和老师的结论并不冲突，关键在于大O表示法会忽略不影响增长趋势的常数系数：

• 针对长度为N的数组，处理第k个元素时，内层循环的次数是2^(k-1)。结合每个循环里复制子集、添加元素的操作成本，最终总操作数的精确值是N*2^(N-1)，这也是你得出O(N2^(N-1))的原因。
• 但2^(N-1)可以写成(1/2)*2^N，在大O表示法中，常数因子（这里的1/2）会被直接忽略——因为我们只关心输入规模N增大时，算法耗时的增长趋势，而非精确的倍数。所以O(N2^(N-1))和O(N2^N)是完全等价的时间复杂度表述。

老师用的是更简洁的标准写法，而你的计算是更精确的常数项展开，两者都正确，只是大O表示法通常会省略这类不影响趋势的常数系数。

内容的提问来源于stack exchange，提问作者Karan Badhwar