Нижние границы сортировок

Нижняя граница сортировок сравнением (comparison-based sorting lower bound) — доказанный теоретический минимум: любой алгоритм сортировки, основанный на попарных сравнениях, требует не менее Ω(n log n) сравнений в худшем случае.

Зачем нужно

Понимание нижних границ объясняет, почему Merge Sort, Heap Sort и Quick Sort (в среднем) оптимальны среди алгоритмов сравнения. Оно также открывает путь к алгоритмам, обходящим нижнюю границу за счёт нечисловых свойств данных — Counting Sort, Radix Sort, Bucket Sort.

Где используется

  • Теоретическая информатика: анализ оптимальности алгоритмов
  • Проектирование алгоритмов: выбор между сортировкой сравнением и без
  • Собеседования: объяснение, почему нельзя «придумать» O(n) алгоритм общей сортировки

Основной контент

Доказательство через дерево решений

Любой алгоритм сортировки n элементов сравнениями можно представить как двоичное дерево решений. Каждый лист — одна из n! возможных перестановок входа. Высота дерева = число сравнений в худшем случае.

Дерево сортировки 3 элементов [a, b, c]:

         a≤b?
        /     \
      b≤c?    a≤c?
     /   \    /   \
  abc   a≤c? bac  ...
        ...

Листьев: n! = 3! = 6 (все перестановки)
Минимальная высота двоичного дерева с n! листьями: ⌈log₂(n!)⌉

Математическое обоснование

Число листьев = n!
Высота двоичного дерева ≥ log₂(n!)

По формуле Стирлинга:
log₂(n!) ≈ n·log₂(n) - n·log₂(e) = Θ(n log n)

Следовательно: любая comparison-based сортировка ≥ Ω(n log n) сравнений

Алгоритмы, преодолевающие нижнюю границу

Эти алгоритмы не используют сравнения элементов и достигают O(n):

// Counting Sort — O(n + k), k — диапазон значений
function countingSort(arr, k) {
  const count = new Array(k + 1).fill(0);
  for (const x of arr) count[x]++;
  const result = ;
  for (let i = 0; i <= k; i++) {
    while (count[i]-- > 0) result.push(i);
  }
  return result;
}
// Работает только для целых чисел в диапазоне [0, k]

// Radix Sort — O(d·(n + k)), d — число цифр
// Bucket Sort — O(n + k) в среднем для равномерно распределённых данных

Сводная таблица

Алгоритм Сложность Ограничение
Merge Sort O(n log n) Нет (сравнение)
Quick Sort O(n log n) средн. Нет (сравнение)
Heap Sort O(n log n) Нет (сравнение)
Counting Sort O(n + k) Целые числа в [0, k]
Radix Sort O(d·(n + k)) Числа с d цифрами
Bucket Sort O(n) средн. Равномерное распределение

Нижняя граница Ω(n log n) применима только к comparison-based алгоритмам.

Почему нельзя придумать O(n) алгоритм сравнения

Предположим, алгоритм делает < n log n сравнений.
Тогда дерево решений имеет высоту < n log n.
Значит, листьев < 2^(n log n).
Но нужно n! ≈ (n/e)^n >> 2^(n log n) листьев.
Противоречие → невозможно.

Частые ошибки

  • Думать, что нижняя граница O(n log n) применима ко всем видам сортировок — Counting Sort обходит её, не делая сравнений.
  • Считать, что O(n log n) достижимо только через рекурсию — Heap Sort O(n log n) и итеративен.
  • Путать нижнюю границу с временной сложностью конкретного алгоритма — нижняя граница — теоретический минимум для класса алгоритмов.
  • Применять Counting Sort при большом диапазоне k >> n — память O(k) неприемлема.

Связанные темы

Ресурсы