Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

№17, Москва, 2008
Авторы: Зубков А.М., Соколов Д.В.
Алгоритмы частичной сортировки множеств сумм
Аннотация:
Частичная сортировка множества чисел состоит в построении упорядоченного по невозрастанию списка части элементов этого множества. Рассматриваются множества двух типов: А) множество 2n сумм элементов по всем подмножествам заданного множества {c1,…,cn} и Б) множество сумм вида a1bσ1+…+anbσn для всех n! перестановок σ =(σ1,…, σn), где {a1,…,an} и {b1,…,bn} — заданные множества. Показано, что построить упорядоченный список из M максимальных элементов множества сумм можно за O(nM) операций в случае А) и за O(nM2) операций в случае Б).
Ключевые слова:
алгоритмы сортировки, множество сумм, список максимальных элементов
Язык публикации: русский, страниц: 10 (с. 225-234)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Зубков Андрей Михайлович,  ,  Математический институт им.В.А.Стеклова РАН
  • Соколов Д.В.,  Математический институт им.В.А.Стеклова РАН