Сложность вложенных циклов

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)

Answer 2

Как сказал @RobinBennet, ответ: O(n * (m + j)).

Внешний цикл повторяется n раз (по одному для каждого элемента).Для каждого элемента во внешних циклах первый внутренний цикл повторяется m раз, а второй j - так что для каждого элемента вы выполняете O (m + j) шагов.Итерировать по n элементам O (n * (m + j).

То есть, предполагая, что m, j не связаны с n - если, например, m = j = n, вы получите O(п ^ 2)