Может ли сложность времени выполнения алгоритма сортировки на основе сравнения быть меньше N logN?

Алгоритмы сортировки — это средства для сортировки заданного набора данных в порядке, соответствующем требованиям пользователя. Они в основном используются для сортировки данных по возрастанию или по убыванию. Существует два типа алгоритмов сортировки:

• Алгоритмы сортировки на основе сравнения
• Алгоритмы сортировки без сравнения

Алгоритмы сортировки на основе сравнения : элементы массива сравниваются друг с другом для сортировки массива. Этот тип алгоритма проверяет, является ли один элемент больше или равным другому элементу в массиве. Он не выполняет манипуляции с одним элементом массива.

Примеры алгоритмов на основе сравнения : сортировка слиянием (сравните элементы и скопируйте их), быстрая сортировка (сравните элементы и поменяйте их местами) и сортировка кучей (соберите элементы в кучу, используя сравнение).

Theorem: Every comparison-based sorting algorithm has the worst-case running time of 

Доказательство:

Предположим, что используется алгоритм сортировки на основе сравнения и массив длины N . Предположим, что входной массив содержит такие элементы массива, как в каком-то беспорядочном порядке. Мы можем упорядочить эти N элементов в N! различные пути.

• Предположения:
  • 1 ^-й элемент имеет N способов упорядочения, 2- ^й элемент имеет (N – 1) способов упорядочения, 3- ^й элемент имеет (N – 2) способов упорядочения и так далее.
    Итак, эти элементы можно расположить в N! способы.
  • Предположим, что количество сравнений, которые этот алгоритм делает в худшем случае, равно K , т. е. максимальное количество сравнений на входном массиве размера N равно K . Чтобы правильно отсортировать все N! Алгоритм возможных входов демонстрирует различные исполнения.
• Доказательство: по принципу голубятни: если n предметов положить в m контейнеры с n > m , то по крайней мере один контейнер должен содержать более одного элемента.
  • Здесь голубь N! разные входы. Дырки ^2к разных исполнений.
  • Если , это означает, что алгоритм выполняется одинаково на 2 разных входных данных, и у нас не может быть общего выполнения алгоритма сортировки, что противоположно к нашему предположению об алгоритме сортировки.
  • Поскольку метод сортировки правильный, 2 ^K ≥ N! ≥ (N/2) ^N/2 , где мы использовали тот факт, что первые N/2 членов N*(N – 1)* … 2*1 не меньше N/2.
  • Беря логарифмическую базу 2 с обеих сторон, K = (N/2)log ₂ (N/2)
  • Следовательно, каждый алгоритм сортировки на основе сравнения имеет наихудшее время работы, которое никогда не может быть лучше, чем .

Для получения более подробной информации см.:
Проектирование и анализ алгоритмов.