O(n log n) - Линеарифмическая Сложность

Проблема

Сортировки вроде Bubble Sort или Insertion Sort работают за O(n²): на 10 000 элементах это уже до 100 000 000 сравнений, счёт идёт на секунды там, где хочется миллисекунды. При этом простой однопроходный O(n) для сортировки в общем случае недостижим - алгоритму нужно как-то сравнить между собой все элементы, а не просто взглянуть на каждый по одному разу. Нужен способ сортировать быстрее квадратичного роста, не выдумывая для этого что-то невозможное вроде настоящего O(n).

Решение

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

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

Формально O(n log n) значит: работа равна n, умноженному на log₂ n - число уровней разбиения. При n = 8 это 8 · log₂ 8 = 8 · 3 = 24. Это именно умножение, а не сложение: log n показывает, во сколько раз n «повторяет» свою O(n)-работу на разных уровнях рекурсии, а не сколько операций добавляется поверх линейного прохода.

Числа растут показательно, но не квадратично. При n = 1 000 работа - около 9 966 операций (1000 · log₂ 1000 ≈ 1000 · 9.97). При n = 1 000 000 - уже 19 931 569, около 19.9 миллиона. Данные выросли в 1000 раз, а работа - примерно в 2000 раз, а не ровно в 1000: лишний множитель дал рост самого log n с 9.97 до 19.93 - почти вдвое. Для сравнения, у O(n²) тот же рост данных в 1000 раз означал бы рост работы в миллион раз - разница на несколько порядков.

Структурно это разделяй-и-властвуй: mergeSort делит массив пополам log₂ n раз, пока не останутся кусочки длиной 1, а merge на каждом уровне честно проходит по всем элементам этого уровня - в сумме n элементов на уровень, независимо от того, сколько кусочков на нём сейчас лежит. Ровно эта пара - «глубина рекурсии log n» и «O(n) работы на уровень» - и даёт произведение n log n.

O(n log n) - это доказанная нижняя граница для любой сортировки, основанной на сравнении пар элементов, а не просто «типичная скорость». Массив из n элементов можно упорядочить n! разными способами, и каждое сравнение делит оставшиеся варианты примерно пополам - значит нужно минимум log₂(n!) сравнений, чтобы отличить один порядок от всех остальных. По формуле Стирлинга log₂(n!) ≈ n log₂ n: быстрее этого предела никакая сортировка сравнением в худшем случае работать не может.

Это объясняет, почему Counting Sort, Radix Sort и Bucket Sort (уже реализованы в разделе сортировок) достигают O(n) и не противоречат этой границе - они не сравнивают элементы друг с другом. Counting Sort раскладывает значения напрямую по индексам счётчика, Radix Sort - по разрядам числа: граница n log n применима только к алгоритмам, которые узнают порядок через сравнения </>, а не через прямой доступ по значению.

На маленьких n разница с O(n) обманчива: при n = 10 log₂ 10 ≈ 3.3 - множитель кажется несущественным, кривые почти сливаются на графике. Но log n растёт без остановки, просто очень медленно - при n = 1 000 000 тот же множитель равен 19.93, и разрыв между O(n) и O(n log n) уже составляет почти 20 раз, а не «почти незаметен», как казалось на маленьких значениях.

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

Сортировка данных общего вида без ограничений - произвольные сравнимые значения, где нельзя воспользоваться трюками вроде Counting Sort (ограниченный диапазон целых) или Radix Sort (фиксированное число разрядов).

Против O(n²) - на любом входе, кроме совсем маленького (примерно до нескольких десятков элементов, где константы перевешивают), O(n log n)-сортировка обгонит Bubble Sort или Insertion Sort.

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

Гарантия против средней скорости - если нельзя допустить деградацию на неудачном входе, стоит выбирать алгоритм с гарантией O(n log n) в худшем случае (Merge Sort, Heap Sort), а не только в среднем (как базовый Quick Sort).

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

Timsort (в разделе сортировок, стандарт сортировки в Python и Java) - гибрид, гарантирующий O(n log n) в худшем случае и ускоряющийся на частично отсортированных данных.

Построение дерева Хаффмана для сжатия данных - на каждом шаге из очереди с приоритетом (кучи) извлекаются два самых редких символа, log n работы на операцию, n операций всего.

Быстрое преобразование Фурье (FFT) - основа цифровой обработки сигналов (аудио, изображения, сжатие MP3/JPEG), сводит вычисление, которое напрямую заняло бы O(n²), к O(n log n) тем же разделяй-и-властвуй приёмом.

Построение выпуклой оболочки (convex hull) в вычислительной геометрии - алгоритмы вроде Quickhull делят точки пополам и объединяют результат, тот же паттерн, что у Merge Sort, только над точками на плоскости.

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

• Когда нужно отсортировать произвольные, ничем заранее не ограниченные данные (сравнимые между собой значения любого типа), и объём данных достаточно велик, чтобы O(n²) стало заметно медленным.
• Когда важна гарантия худшего случая, а не только средняя скорость - Merge Sort и Heap Sort не деградируют на неудачных входных данных, в отличие от некоторых O(n log n)-в-среднем алгоритмов.

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

• Array.prototype.sort в V8 и стандартные сортировки Python/Java - все построены на вариантах O(n log n) (Timsort, уже реализованный в разделе сортировок).
• Быстрое преобразование Фурье (FFT) в обработке звука и сжатии сигналов - тот же принцип «разделяй пополам, объединяй за O(n)», но применённый не к сортировке, а к вычислению спектра.