Сложность алгоритмов сортировки на частично упорядоченных множествах

• Автор: Никитин, Юрий Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 80 с. : ил

Содержание
1 Введение
1.1 Краткие исторические сведения
1.2 Постановка задачи
1.3 Основные результаты
2 Сортировка декартовых произведений частично упорядоченных множеств
2.1 Автоморфизмы декартовых произведений частично упорядоченных множеств
2.2 Нижняя оценка L(M X ... х Мп)
2.3 Верхняя оценка L(M X ... х Мп)
3 Сортировка сумм частично упорядоченных множеств
3.1 Нижняя оценка L(M + N)
3.2 Верхняя оценка L(M + N)
3.3 Нижняя оценка L(nM)
3.4 Верхняя оценка L(nM)
3.5 Анализ качества полученных оценок L(ггМ)
3.5.1 Анализ нижней оценки
3.5.2 Асимптотическая оценка L(mLk)
3.5.3 Анализ верхней оценки
4 Сложность извлечения информации из частично упорядоченных множеств
4.1 Возможность достижимости минимума сложности извлечения информации из частично упорядоченных множеств
4.1.1 Достижимость в среднем
4.1.2 Оценка для семейства МП)ГП^
4.2 Плотность сложности извлечения информации из частично
упорядоченных множеств
4.3 Достижимость максимума сложности извлечения информации из частично упорядоченных множеств
4.4 Неустойчивость сложности извлечения информации к удалению элементов из частично упорядоченного множества
Литература

1 Введение
1.1 Краткие исторические сведения
Задача сортировки является одной из известнейших задач теории алгоритмов. Как пишет Кнут в своей монографии [5]: ”... история сортировки была тесно связана со многими нехоженными тропами в вычислениях: с первыми машинами для обработки данных, первыми запоминаемыми программами, первым программным обеспечением, первыми методами буферизации, первой работой по анализу алгоритмов и сложности вычислений.”
В классической постановке задача сортировки состоит в поиске для данных п чисел х,... ,хп перестановки тг £ 5(п), при которой последовательность чесел .., Хх(п) упорядочена по восрастанию. Под сложностью
алгоритма сортировки подразумевают количество необходимых ему сравнений в худшем случае. Из мощностных соображений сложность произвольного алгоритма сортировки оценивается снизу через к^2 (го!).
Впервые потребность в быстрой сортировке больших объемов информации возникла в связи с переписью населения в Соединенных Штатах. И уже в конце XIX века появились первые электромеханические сортировочные машины. Таким образом, исторически первой возникла поразрядная сортировка. Как только в начале 40-х годов на сцене появились ЭВМ — разработка методов сортировки тесно переплелась с их развитием. Стали появляться различные модификации сортировки слиянием и вставками сложности 0(по%п) для п элементов, а также возникло естественное разделение на внутреннюю и внешнюю сортировки. Расцвет борьбы за качество алгоритмов решения задачи сортировки приходится на 50-е и 60-е годы. Именно тогда были изобретены столь широко известный метод Шелла, быстрая сортировка Хоара, пирамидальная сортировка и сортировка вставками в дерево.
Характерным этапом этих масштабных исследований задачи сортировки можно считать монографию Кнута [5], в которой систематизировано множество имеющихся на тот момент подходов к этой задаче. Дальнейшие исследования задачи сортировки на линейных порядках развивались по следующим трем основным направлениям.
Во-первых, это работы по улучшению качества классических алгоритмов сортировки. Исследователи старались более тонко подогнать параметры уже известных методов [21] или умело скомбинировать несколько

методов в одном алгоритме (например, цифровой сортировки и сортировки слиянием) [16, 24].
Во-вторых, изучались различные подклассы входных последовательностей, на которых время работы алгоритмов сортировки существенно меньше, чем в общем случае. В качестве входного набора брали последовательность сумм чисел из ограниченного множества [17] или, например, класс частично отсортированных последовательностей [19].
Третьим, наиболее интенсивно развивающимся направлением является решение задачи сортировки в классе параллельных алгоритмов. Для модели PRAM были придуманы как оригинальные алгоритмы [22], так и обобщения ранее известных парадигм (например, сортировки слиянием [14]). Кроме того, алгоритмы сортировки конструировались для сортирующих сетей [25] и многомерных вычислительных решеток [15, 23].
Относительно недавно стали появляться работы, в которых задача сортировки исследуется на частично упорядоченных множествах [6, 7, 8, 9, 10, 20]. Были сформулированы три смежные задачи: задача сортировки частично упорядоченного множества М (используя результаты попарных сравнений элементов множества М установить порядок его элементов зная, что множество М изоморфно известному образцу Mq,) задача распознавания частично упорядоченного множества М (определить, является ли множество М изоморфным множеству Mg) и задача определения порядка на множестве М (без априорной информации). Приведем основные результаты по задаче сортировки частично упорядоченных множеств за этот период.
Для нескольких семейств частично упорядоченных множеств были получены точные значения сложности сортировки. В частности было доказано, что если множество М состоит из п — 2 попарно несравнимых элементов и одной 2-х элементной цепи, то сложность его сортировки равна [20]. Была установлена асимптотика п2п сложности сортировки для n-мерного двоичного куба Вп [6, 20]. Кроме того в [20] было показано, что сложность сортировки частично упорядоченного множества М мощности п и ширины w заключена между п log3 п — п log3 w — 5п и 2wn log2 n + 3wn.
1.2 Постановка задачи
Поставим задачу сортировки для частично упорядоченных множеств (далее — ЧУМ). Множество М = {#i,... ,жт} называется частично упорядоченным [2], если на его элементах задано отношение частичного порядка

пт — 1 сравнений мы нашли один из п максимальных элементов множества пМ. Далее, за пт — 1 сравнений мы можем выделить из ЧУМ пМ ЧУМ {х Є пМ : х < у пт} и его дополнение {х € пМ : х?упт}. Следовательно, за 2пт — 2 сравнений мы разбили ЧУМ пМ на два ЧУМ, одно из которых изоморфно М (и для которого нам известен максимальный элемент), а другое изоморфно (п — 1 )М. В итоге, за 2пт — 2 + Ь(М) сравнений задача сортировки ЧУМ пМ может быть сведена к задаче сортировки ЧУМ (п — 1 )М. Получаем оценку:
ЦпМ) < 2пт -2 + £М(М) + Ь((п - 1 )М) <
< 2т ^ і — 2(п — 1) + пЬ{г)(М) = (п2 + п — 2)т — 2(п — 1) + пЬ^гМ).

Теорема доказана.
Следствие. Пусть для некоторого ЧУМ М верно, что М > 2 и | тах(М)| = 1. Тогда при п —>■ оо справедлива оценка
~М<,ЦпМ)&п2М.
Доказательство. Из условия |тах(М)| = 1 следует связность графа диаграммы Хассе ЧУМ М. Для доказательства остается воспользоваться теоремой 9, теоремой 10 и утверждением 18. Следствие доказано.
Теорема 11. Пусть дано ЧУМ М со связным графом диаграммы Хассе. Положим т — М и к = | тах(М)|. Тогда при и Є N справедлива оценка
Ь(пМ) < 2п2тк — пк(пк + 1) + пЬ^ТМ).
Доказательство. При т = 1 утверждение теоремы верно. Далее предполагаем т > 2. Пусть Мд = пМ. Для і Є {1,...,пк} рассмотрим последовательность операций уі Є тах(Мі_і), £/; = {х Є і : х < г/;}, Мі = М,_і Д. Она приводит нас к разложению пМ — П 11 •.. и иі и Мі и тождеству Мпь — 0. Как и в теореме 10, на поиск элемента у,: уйдет |М;_і| - 1 сравнений. Столько же сравнений уйдет на разделение ЧУМ Мі-і на ЧУМ ііі и ЧУМ А&
Будем называть два максимальных элемента ж, у Є пМ соседними по компоненте связности, если {г Є пМ : г < і} П {г 6 пМ : г < у} 0. Обозначим это отношение соседства через Б. При т > 2 отношение в рефлексивно, кроме того оно симметрично, следовательно транзитивное замыкание отношения 5 порождает отношение эквивалентности ” ~ ” со