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

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)你的情况,因为每个i从0给n我们做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次数.大哦忽略常数,所以2n = O(n).

由于它们不是嵌套的,因此每个运行的次数将不依赖于另一个.因此,您添加迭代次数,而不是将它们相乘.