81
правка
Изменения
+ для рандомизированных алгоритмов
Итак, для любого алгоритма сортировки сравнениями, существует такая перестановка, на которой он выполнит <tex>\Omega(n \log n)</tex> сравнений, ч. т. д.
}}
Если алгоритм сортировки является рандомизированным, то для него справедливо, что нижняя граница матожидания времени работы для сортировки сравнениями <tex>n</tex> элементов ровна <tex> \Omega(n \log n) </tex>. Доказательство этой теоремы можно прочесть в Кормене.
==Источники==
