Изменения
Нет описания правки
Заметим так же, что число листьев у этого дерева должно быть не меньше <tex>n!</tex>, иначе одна из перестановок не сможет быть определена.
Число сравнений в наихудшем случае будет равно глубине этого дерева, поэтому осталось показать, что эта глубина есть <tex>\Omega(n \log n)</tex>. Для этого заметим, что у двоичного дерева глубины <tex>n</tex> листьев не больше <tex>2^n</tex> (в случае полного двоичного дерева), т. е. у двоичного дерева с <tex>n</tex> листьям глубина по крайней мере <tex>\lceil \log_2 n! \rceil</tex>. Осталось оценить <tex>\log_2 n ! = \log_2 1 + \log_2 2 + \ldots + \log_2 n ></tex><tex>n/2 \log_2 (n/2) = n/2(\log_2 n - 1)=\Omega (n \log n)</tex>
Итак, для любого алгоритма сортировки сравнениями существует такая перестановка, на которой он выполнит <tex>\Omega(n \log n)</tex> сравнений, ч. т. д.
