循环可以影响其他循环的复杂性而不在其中吗？

Question

一个循环可以影响任何其他循环但不在其中吗？

代码的总时间复杂度会改变吗？

我在互联网上找到这段代码作为我正在谈论的示例：

int i, j, k, val=0, c=0;
for (int i=n; i>1; i=i/2)
    val++;
for (j=1; k<val; j=j*2)
    c++;

我认为这段代码的时间复杂度是 n^2，但看来我错了

对不起我的英语。

Answer 1

是的，可以，在您的示例中，可以。第一个循环计算一些用于确定第二个循环将执行的迭代次数的值。迭代次数与复杂度（密切相关）。

目前，第一个循环执行 ~log(n) 次迭代，第二个循环执行 ~log(log(n)) 次迭代。如果将第一个循环更改为执行 ~n 次迭代，则第二个循环将执行 ~log(n)。如果将第一个更改为以使其成为 ~2^n 的方式计算 val，则第二个循环将执行 ~n 次迭代。

这个其他代码是一个循环并没有什么特别之处：循环之前的任何代码都会影响循环的复杂性。