Что означает O(N²)?

Что такое O(N²)?

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

Примеры алгоритмов с O(N²)

• Пузырьковая сортировка (Bubble Sort)
• Сортировка вставками (Insertion Sort) в худшем случае
• Проверка всех пар элементов в массиве

Пример кода

function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // меняем местами
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

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

Когда это важно?

O(N²) — это медленная сложность для больших N. Если N = 1000, то потребуется около 1 000 000 операций. Для N = 10 000 — уже 100 000 000 операций. Поэтому алгоритмы с O(N²) применяются только для небольших наборов данных или когда другие алгоритмы не подходят.

Вывод: O(N²) — это квадратичная сложность, которую следует избегать для больших данных. Если возможно, используйте алгоритмы с O(N log N) или O(N).