多个循环是否与嵌套循环具有相同的复杂性？

Question

这个for循环的复杂度为O(n)

for ($i=0; $i < $arrCount - 1; $i++) { }

而这 2 个嵌套 for 循环的复杂度为 O(n^2)

for ($i=0; $i < $arrCount; $i++) { 
  for ($j=0; $j < $arrCount; $i++) { 
  }
}

但是，如果我在一个函数中执行了 2 个 for 循环，并且它们只是相互跟随，没有嵌套，那会怎样呢

for ($i=0; $i < $arrCount; $i++) { 
}
for ($i=0; $i < $arrCount; $i++) { 
}

该函数是否仍会在 O(n) 后执行？

Answer 1

是。

嵌套循环意味着外层循环将在（外层的）每次迭代中完全执行内层循环。在您的情况下，这意味着 O(n^2)，因为对于从 0 到 n 的每个 i，我们都会执行 n 操作。

i = 0 => inner loop runs n iterations
i = 1 => inner loop runs n iterations
...
i = n - 1 => inner loop runs n iterations

n 次迭代 n 次意味着 n^2 次总迭代，因此 O(n^2).

你的 2 个没有嵌套的循环将每次迭代 n 次，总共 2n 次。 Big-oh 忽略常量，所以 2n = O(n).

由于它们不是嵌套的，因此每个运行的次数将不依赖于另一个。所以你添加迭代次数，而不是乘以它们。

Do multiple loops have same complexity as nested loops?