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

Проблема

Задачи вроде «сравнить каждый элемент с каждым другим» (найти дубликаты, отсортировать без лишней памяти, посчитать расстояние между всеми парами точек) естественным образом наводят на код с двумя вложенными циклами. На 10 элементах это 45 сравнений - мгновенно. На 10 000 - уже под 50 000 000, и разница между «работает» и «зависает» здесь не постепенная, а обвальная. Нужно уметь заранее увидеть эту опасность в коде, а не после того, как проект столкнётся с реальными объёмами данных.

Решение

Алгоритм - O(n²), если в нём есть два вложенных цикла, и оба зависят от размера входа n: внешний проходит по n элементам, а внутри каждой его итерации - ещё один проход, тоже по n (или почти по n) элементам. Итоговое число операций - произведение n · n = n². Узнать такой код просто: если убрать один из циклов, второй сам по себе был бы обычным O(n) - именно вложенность, а не сами циклы по отдельности, и даёт квадрат.

Как это работает

Формально O(n²) означает: работа не превышает c · n² для некоторой константы c, начиная с какого-то размера входа. У bubbleSort точное число сравнений - n(n - 1) / 2, то есть c = 1/2. Это тот же порядок роста, что и у n² без множителя - Big O описывает форму кривой, а не точный коэффициент перед ней.

Числа растут пугающе быстро. При n = 1 000 - около 499 500 сравнений, меньше полумиллиона, ещё терпимо. При n = 1 000 000 - уже 499 999 500 000, то есть почти полтриллиона. Данные выросли в 1000 раз, а работа - примерно в 1 000 000 раз, а не в 1000: рост здесь квадратичный по отношению к росту самих данных, k² при k-кратном увеличении n.

Структурно причина всегда одна: два цикла, вложенных друг в друга, и оба зависящие от n. У bubbleSort внешний цикл проходит по i от 0 до почти n, а внутри каждой его итерации - ещё цикл по j, тоже до почти n. Если убрать внешний цикл и оставить только внутренний, получился бы обычный O(n) проход - именно комбинация двух таких проходов и даёт квадрат.

O(n²) не обязательно означает «ровно n²»: n(n - 1) / 2 (треугольное число, как у bubbleSort), 3n², n² / 4 - всё это один и тот же класс O(n²), потому что все они растут пропорционально квадрату n с точностью до постоянного множителя. Отличать их по названию бессмысленно - важна форма кривой, а не число перед n².

Сортировка не обязана быть O(n²) - Merge Sort и другие алгоритмы разделяй-и-властвуй (уже разобраны в материале про O(n log n)) решают ту же задачу за n log n, заметно быстрее при больших n. Но на маленьких массивах (примерно до пары десятков элементов) простой вложенный цикл Bubble Sort или Insertion Sort часто оказывается быстрее на практике - у рекурсии mergeSort есть собственные накладные расходы, которые перевешивают выигрыш от log n, пока n не станет достаточно большим.

Некоторые задачи, которые выглядят как «нужно сравнить всё со всем», на самом деле не обязаны быть O(n²) - построение выпуклой оболочки (уже упомянуто в материале про O(n log n)) наивно кажется перебором всех пар точек, но алгоритмы вроде Quickhull решают её за n log n, находя структуру в задаче вместо честного перебора. Настоящий O(n²) остаётся только там, где такой структуры нет и сравнить действительно нужно каждую пару - например, точный расчёт попарных расстояний между всеми точками.

Нюансы выбора

Малые и умеренные n - до нескольких тысяч элементов, где абсолютное время выполнения всё ещё измеряется миллисекундами, а не секундами или минутами.

Задачи, генуинно требующие всех пар - попарные расстояния, коллизии, корреляционные матрицы - там, где для конкретной задачи не существует более быстрой структуры.

Против O(n log n) - как только n выходит за пределы «маленького» (обычно уже на паре тысяч элементов), для сортировки и похожих задач почти всегда стоит переходить на алгоритм с более быстрым классом сложности.

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

Примеры в коде

Bubble Sort, Insertion Sort и Selection Sort (в разделе сортировок) - три классических примера квадратичной сортировки через вложенный цикл, каждый со своим вариантом того, что именно повторяется на внутреннем проходе.

Наивные физические движки - проверка коллизий каждого объекта с каждым другим (for i { for j { ... } }) без пространственного разбиения даёт O(n²) на числе объектов сцены.

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

Наивное сравнение строк на схожесть (например, посимвольное сравнение всех пар строк в списке без индекса) - количество пар растёт как n², даже если сравнение одной пары само по себе быстрое.

Когда применять

• Когда n заведомо маленькое или умеренное (примерно до нескольких тысяч) и простота кода важнее выжимания последних миллисекунд.
• Когда задача по своей природе требует сравнить все пары элементов между собой (расстояние между всеми точками, попарные коллизии) и более быстрой структуры для неё нет.

Примеры из практики

• Bubble Sort и Insertion Sort (в разделе сортировок) - классические примеры вложенного цикла, дающего O(n²) в среднем и худшем случае.
• Наивная проверка на дубликаты двумя вложенными циклами (for x of arr { for y of arr { ... } }) - до появления Set или хеш-таблицы это был стандартный подход.