java - 为什么 2 for 循环的时间复杂度不是 O(n*2^n)？

Question

此方法的时间复杂度为 O(2^n)根据我的教授。

我觉得这个方法的时间复杂度应该是O(n * 2^n)因为

外部 for 循环成本 O(n)
内部 for 循环成本 O(2^n)

public static int loop(int n) {
    int j = 1;
    for (int i = 0; i < n; i++) {
        for (int k = j; k > 0; k--) {
            System.out.println("Hello world");
        }
        j *= 2;
    }
    return j;
}

Answer 1

考虑一下:

对于 i = 0 :j = 1 -> 2^0
对于 i = 1 :j = 2 -> 2^1
对于 i = 2 :j = 4 -> 2^2
对于 i = 3 :j = 8 -> 2^3....

对于 i = n-1 :j = 2^n-1
如果您添加所有这些:

2^0 + 2^1 + 2^2 +.....+2^(n-1) => order of 2^(n) -> 2^(n) - 1 to be precise

所以时间复杂度是 O(2^n)