635
правок
Изменения
Нет описания правки
{{
Теорема
|about=о нижней оценке для сортировки сравнениемсравнениями
|statement=В худшем случае любой алгоритм сортировки сравнениями выполняет <tex>\Omega(n \log n)</tex> сравнений, где <tex>n</tex> {{---}} число сортируемых элементов.
{{Утверждение
|statement=Пирамидальная сортировка и сортировка слиянием являются асимптотически оптимальными сортировками сравнением.
|proof=Верхние границы <tex> O(n \log n) </tex> времени работы пирамидальной сортировки и сортировки слиянием совпадают с нижней границей <tex>\Omega(n \log n)</tex> для наихудшего случая из теоремы о нижней границе для сортировки сравнениемсравнениями.
}}
