Частичная сортировка множества чисел состоит в построении упорядоченного по невозрастанию списка части элементов этого множества. Рассматриваются множества двух типов: А) множество 2ⁿ сумм элементов по всем подмножествам заданного множества {c₁,…,c_n} и Б) множество сумм вида a₁b_σ1+…+a_nb_σn для всех n! перестановок σ =(σ₁,…, σ_n), где {a₁,…,a_n} и {b₁,…,b_n} — заданные множества. Показано, что построить упорядоченный список из M максимальных элементов множества сумм можно за O(nM) операций в случае А) и за O(nM²) операций в случае Б).

алгоритмы сортировки, множество сумм, список максимальных элементов

Математические вопросы и теория численных методов