Почему вложенные циклы имеют сложность O(N²)?

Что такое O(N²) и почему вложенные циклы приводят к такой сложности?

Когда мы говорим о вычислительной сложности алгоритма, мы оцениваем, как количество операций растёт с увеличением размера входных данных. O(N²) — это квадратичная сложность, при которой число операций пропорционально квадрату размера данных.

Вложенные циклы — классический пример такой ситуации. Представьте, что у вас есть массив из N элементов, и вы хотите сравнить каждый элемент с каждым другим. Внешний цикл проходит по всем N элементам, а для каждого из них внутренний цикл снова проходит по N элементам. В итоге получается N × N = N² операций.

Пример на JavaScript

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {      // внешний цикл: N раз
    for (let j = 0; j < arr.length; j++) {    // внутренний цикл: N раз
      console.log(arr[i], arr[j]);            // всего N² операций
    }
  }
}

Если массив содержит 10 элементов, будет 100 выводов в консоль. Если 100 — уже 10 000. Рост очевиден.

Где это применяется?

• Сортировка пузырьком (Bubble Sort) — O(N²) в худшем случае.
• Поиск дубликатов в неотсортированном массиве без дополнительной памяти.
• Перебор всех пар в задачах комбинаторики.

Вывод

Понимание O(N²) помогает избегать неэффективных решений при работе с большими данными. Если можно заменить вложенные циклы на более эффективные алгоритмы (например, с использованием хеш-таблиц для O(N)), это стоит сделать. Квадратичная сложность приемлема только для маленьких массивов или когда других вариантов нет.