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

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 但似乎我错了

对不起我的英语不好。

标签： performancetimetime-complexity

Answer 1

是的，它可以，在你的例子中，它确实如此。第一个循环计算一些值，用于确定第二个循环将执行的迭代次数。迭代次数与复杂性密切相关。

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

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