`continue` 语句的复杂度是多少？

Question

我知道这是一件非常简单的事情，但它只是在我思考一个更大的问题时突然想到的。另外，如何验证它？

List<int> items = new List(){10, 11, 32, 1, 101};

for(int x = 0; x < items.Length; x++)
{
   for(int y = 0; y < items.Length; y++)
   {
     continue;
   }
}

Answer 1

Continue 本身对复杂度没有影响，因为它必须（在恒定时间内）作为循环迭代的一部分执行，并且相应的循环仍然具有相同的复杂度，无论它是否具有 continue或者不是（即你的样本的内循环仍然是 O(len_items) ）

如果有代码在某些情况下会有条件地执行并且continue缩短一些迭代，则可能会影响复杂性：

for(int x = 0; x < items.Length; x++)
{
    if (x > 3 ) 
         continue; // outer continue
    for(int y = 0; y < items.Length; y++)
    {
       continue; // inner continue
    }
}

"outer continue" 将影响（与 goto 相同或 if 的倒数）整个操作的性能 - 在这种情况下 O(n) 因为外循环最多运行内循环3 次 - O(n + 3*n) 与 O(n) 相同。

"inner continue" 对性能估计没有影响，因为无论如何每个项目的循环都必须是运行。

类似的推理适用于 break - 不会影响性能估计，除非它在循环的某个一致部分缩短循环（即总是在检查 N 中的 log N 项后停止）。

`continue` 语句的复杂度是多少？

What is the complexity of a `continue` statement?

c#

complexity-theory

for-loop

continue

time-complexity