O(n²) — Квадратичная сложность

Определение

Квадратичная сложность означает, что время выполнения алгоритма пропорционально квадрату размера входных данных.

Формула

$O(n^2)$

Характеристики

• Два вложенных цикла по n элементов
• Время растет квадратично
• Плохо масштабируется
• Приемлемо только для малых данных

Визуализация вложенных циклов

Для массива из 4 элементов [A, B, C, D]:

i=0, j->  A-B  A-C  A-D     (3 операции)
i=1, j->  B-C  B-D           (2 операции)
i=2, j->  C-D                (1 операция)
         -----------
         Итого: 6 операций = 4×3/2 ≈ n²/2 = O(n²)

Полная матрица сравнений:
     A   B   C   D
A    ·   ✓   ✓   ✓
B    ·   ·   ✓   ✓
C    ·   ·   ·   ✓
D    ·   ·   ·   ·

Половина матрицы = n²/2, но O(n²)

Квадратичный рост

n = 2  -> операций = 4    [●●●●]
n = 3  -> операций = 9    [●●●●●●●●●]
n = 4  -> операций = 16   [●●●●●●●●●●●●●●●●]
n = 5  -> операций = 25   (слишком много для визуализации)
n = 10 -> операций = 100  (не поместится!)

Сравнение производительности

Размер (n)	n	n log n	n²	Разница с O(n)
10	10	33	100	10×
100	100	664	10,000	100×
1,000	1,000	9,966	1,000,000	1000×
10,000	10,000	132,877	100,000,000	10,000×

График сложности

Операции
      |
100K  |                                ●  O(n²)
      |                              ●
 75K  |                            ●
      |                          ●
 50K  |                        ●
      |                      ●
 25K  |                  ● ●
      |              ● ●
 10K  |          ● ●
      |      ● ●  O(n log n)
   1K | ● ●●  O(n)
      |
   0  +--------------------------------------------->
        10   50   100   250   500   1000        n

Когда O(n²) приемлемо?

✅ Хорошие случаи

• Массивы до 1000 элементов
• Данные почти отсортированы (Insertion Sort эффективна)
• Простота кода важнее производительности
• Обучение и прототипирование

❌ Плохие случаи

• Большие объемы данных (> 10,000 элементов)
• Производственный код с неизвестным размером входных данных
• Реал-тайм системы
• Часто выполняемые операции

Оптимизация алгоритмов O(n²)

До: O(n²)

function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

После: O(n)

function hasDuplicates(arr) {
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

Сравнение алгоритмов сортировки

Алгоритм	Лучший	Средний	Худший	Память
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)

Важно помнить

✅ Простота реализации ✅ Подходит для малых данных ✅ Некоторые O(n²) алгоритмы эффективны на почти отсортированных данных ❌ Очень плохо масштабируется ❌ Неприемлемо для больших данных ❌ Часто можно оптимизировать до O(n log n) или O(n)

Примеры кода

1. Сортировка пузырьком (Bubble Sort)

function bubbleSort(arr) {
  const n = arr.length;
 
  for (let i = 0; i < n; i++) {           // Внешний цикл: n итераций
    for (let j = 0; j < n - i - 1; j++) { // Внутренний цикл: n итераций
      if (arr[j] > arr[j + 1]) {
        // Меняем местами
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
 
  return arr;
}
 
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

2. Сортировка выбором (Selection Sort)

function selectionSort(arr) {
  const n = arr.length;
 
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
 
    // Ищем минимальный элемент
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
 
    // Меняем местами
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
 
  return arr;
}

3. Сортировка вставками (Insertion Sort)

function insertionSort(arr) {
  const n = arr.length;
 
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
 
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
 
    arr[j + 1] = key;
  }
 
  return arr;
}

4. Поиск всех пар элементов

function findAllPairs(arr) {
  const pairs = [];
 
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      pairs.push([arr[i], arr[j]]);
    }
  }
 
  return pairs;
}
 
console.log(findAllPairs([1, 2, 3]));
// [[1, 2], [1, 3], [2, 3]]

5. Проверка на дубликаты (наивный подход)

function hasDuplicatesNaive(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}
 
console.log(hasDuplicatesNaive([1, 2, 3, 2])); // true

6. Поиск ближайшей пары

function closestPair(points) {
  let minDist = Infinity;
  let pair = null;
 
  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      const dist = Math.sqrt(
        Math.pow(points[i].x - points[j].x, 2) +
        Math.pow(points[i].y - points[j].y, 2)
      );
 
      if (dist < minDist) {
        minDist = dist;
        pair = [points[i], points[j]];
      }
    }
  }
 
  return pair;
}