И. С. Сергеев, “О верхней границе сложности сортировки”, Ж. вычисл. матем. и матем. физ., 2021, том 61, номер 2,страницы 345

Информатика

О верхней границе сложности сортировки

И. С. Сергеев

125438 Москва, 4-й Лихачёвский пер., 15, ФГУП "НИИ "Квант", Россия

Аннотация: Показано, что для сортировки набора из $n$ элементов линейно упорядоченного множества всегда достаточно $\log_2(n!)+o(n)$ попарных сравнений. Библ. 14. Фиг. 3.

Ключевые слова: сортировка, сложность, дерево решений, частичный порядок, симплекс.

УДК: 519

Поступила в редакцию: 18.09.2019
Исправленный вариант: 23.07.2020
Принята в печать: 16.09.2020

DOI: 10.31857/S0044466921020125