c# - 嵌套循环复杂度

Question

我有这个 C# 方法:

private void Process()
{

  foreach (Vat vat in vats) // n elements
  {
    foreach (ProcessResultRow row in processResultRows) // m elements
    {
      // something here
    }

    foreach (KeyValuePair<int, Shop> entry in _shopsList) // j elements
    {
      // something else here
    }
  }

}

我知道两个嵌套循环的复杂度为 O(n^2)。这个例子对吗？

我犹豫不决，因为在外部循环中我有两个相同级别的循环。

Answer 1

如果循环没有return、break 和类似的东西(例如抛出异常)，那么复杂性是

O(n * (m + j)) == O(n * m) + O(n * j)

如果 m 和 j 都是常量我们有

O(n*m + n*j) == m * O(n) + j * O(n) == O(n)  

如果至少有一个 m 或 j 使得 m ~ n 或 j ~ n 那么我们有

// here m ~ n and j is some const
O(n * m) + O(n * j) == O(n * n) + j * O(n) == O(n**2) + O(n) == O(n**2)