Какая временная сложность у алгоритма полного перебора с двумя вложенными циклами?

Временная сложность классического полного перебора с двумя вложенными циклами, каждый из которых зависит от размера входных данных n, составляет O(n²) (квадратичная сложность).

Пример на JavaScript/Node.js:

// O(n²)
for (let i = 0; i < n; i++) {       // Внешний цикл: O(n)
  for (let j = 0; j < n; j++) {     // Внутренний цикл: O(n)
    // Какая-то операция O(1)
    console.log(`Pair: ${i}, ${j}`);
  }
}
// Общее количество итераций: n * n = n²

Вариации:

• Если размеры массивов разные (n и m), сложность будет *O(n m)**.

  // O(n * m)
  const arr1 = new Array(n);
  const arr2 = new Array(m);
  for (let i = 0; i < arr1.length; i++) {
  for (let j = 0; j < arr2.length; j++) {
  // Операция
  }
  }

• Если внутренний цикл начинается с i+1 (например, для сравнения всех уникальных пар), сложность остаётся O(n²), но количество итераций будет примерно n²/2, что в асимптотическом анализе всё равно O(n²).

Квадратичная сложность считается неэффективной для больших данных, и в production-коде на Node.js для подобных задач часто ищут оптимизации (кеширование, хеш-таблицы, более эффективные алгоритмы).