此方法的时间复杂度为 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;
}
最佳答案
考虑一下:
对于 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)
关于java - 为什么 2 for 循环的时间复杂度不是 O(n*2^n)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60565484/