Изменения
Нет описания правки
Для начала введём некоторые обозначения.
Пусть <tex>S_n</tex> {{---}} множество перестановок элементов массива длины <tex>n</tex>. Будем считать перестановки строками в <tex>\Sigma^*_n</tex>, где <tex>\Sigma_n=\{1, 2, \ldots, n\}</tex>. Введём [[Бинарное отношение | бинарное отношение ]] <tex>R: \Sigma^*_n \rightarrow \Sigma^*_n</tex>: <tex>\pi R\sigma</tex> тогда и только тогда, когда <tex>\pi =xy</tex> и <tex>\sigma =x^Ry</tex>, где <tex>\pi, \sigma \in \Sigma^*_n</tex> и <tex>x^R</tex> обозначает развёрнутую <tex>x</tex>.
Пусть <tex>\pi</tex> {{---}} перестановка, тогда <tex>f(\pi)</tex> {{---}} наименьшее <tex>k</tex> такое, что существует последовательность перестановок <tex>\pi_0 R \pi_1 R \ldots R \pi_k = e_n</tex>, где <tex>e_n = 123\ldots n</tex>. Тогда для числа <tex>n</tex> будем обозначать <tex>f(n)</tex> за максимальное <tex>f(\pi)</tex> среди всех <tex>\pi \in S_n</tex>.
{{Теорема
|statement=Число разворотов, необходимое для сортировки последовательности <tex>f(\chi ) \geqslant </tex>, не меньше <tex>\dfrac{17n}{16}</tex>
}}
[[Категория: Сортировки]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Другие сортировки]]
