据我所知,当你写一个类似于这个的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 循环的算法,其中内部计数变量取决于外部计数变量,您是否应该担心这会对算法的复杂性造成什么影响?
最佳答案
“如果我说错了请指正。”
你错了。
您可以在“第一个”循环的某处添加 i++
,这会“破坏”您的代码。当然会执行 i
与 SOME_NUM
的比较。
关于for 循环与 while 循环的 C++ 行为,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23986847/