for 循环与 while 循环的 C++ 行为

Question

据我了解，当你写一个类似于这个的for循环时

for (int i = 0; i < SOME_NUM; i++) { 
  if (true)
    do_something();
  else
    do_something_else();
}

此操作的时间复杂度主要受

if (true)

语句影响，因为 for 循环迭代实际上并不涉及

i

与

SOME_NUM

的任何比较，编译器本质上只是运行 for- 内的代码循环

SOME_NUM

次。 如果我错了请纠正我。

但是，如果这是正确的，那么以下嵌套 for 循环的行为如何？

for (int i = 0; i < SOME_NUM; i++) {
  for (int j = 0; j < i; j++) {
   do_something();
  } 
}

内部 for 循环中的

j

现在的上限为

i

，该值在每次循环重新启动时都会更改。编译器将如何编译这个？这些嵌套的 for 循环本质上表现得像一个内部带有 while 循环的 for 循环吗？如果您正在编写一个使用嵌套 for 循环的算法，其中内部计数变量取决于外部计数变量，您是否应该担心这会对算法的复杂性产生什么影响？

Answer 1

“如果我错了，请纠正我。”

你错了。

您可以在“第一个”循环中的某个位置添加

i++

，这会“破坏”您的代码。当然会进行

i

与

SOME_NUM

的比较。

Answer 2

此操作的时间复杂度主要受 if (true) 语句影响，因为 for 循环迭代实际上并不涉及 i 与 SOME_NUM 的任何比较，编译器实际上只会运行 for 循环内的代码 SOME_NUM 次。如果我错了，请纠正我。

是的，你错了。在每次迭代开始时，

i

都会递增，并检查条件表达式

i < SOME_NUM

。

如果您正在编写一个使用嵌套 for 循环的算法，其中内部计数变量取决于外部计数变量，您是否应该担心这会对算法的复杂性产生什么影响？

是的。在这种情况下就必须考虑嵌套的影响。所以，最好你应该删除嵌套。

Answer 3

我想你应该学习基本循环结构。循环结构有一个条件语句，它指示是否进入循环以及迭代多少次。

if(true)

只是指示是否执行以下语句（在本例中将执行，因为条件始终为真）。

总而言之，第一个循环将执行

SUM_NUM

次（

O(SUM_NUM)

），第二个循环是一个

O(n^2)

循环。