循环运行到 2 的 n 次方的时间复杂度是多少

Question

循环运行到 2 的 n 次方的时间复杂度是多少？请参阅下面的代码片段。

int[] arr={1,2,3,4};
for(int i=0;i<arr.length;i++){
    for(int j=0;j<Math.pow(2,i);j++){
        System.out.println(j);
    }
}

Answer 1

如果你在数组中有n个元素，你将执行

2^0 = 1 computation in first loop
2^1 = 2 computation in second loop
2^2 = 4 computation in third loop
...
2^(n-1) = 2^(n-1) computation in n-th loop

将你得到的所有这些相加 2^0 + 2^1 + 2^2 + ... + 2^(n-1) = 2^n-1几何级数总和的公式。所以你的时间复杂度是O(2^n)