74
правки
Изменения
Нет описания правки
Итоговая сложность алгоритма {{---}} <tex> O(n) + O(n^2) </tex> на преподсчет.
== Разбиения на множества ==
=== Разбиение на <tex> k </tex> подмножеств ===
Рассмотрим множество первых <tex> n </tex> натуральных чисел: <tex> N_n = \{1, 2, ..., n\} </tex>. Необходимо разбить его на <tex> k </tex> непустых подмножеств <tex> \{B_1, B_2, ..., B_k\} </tex> с равным распределением вероятности.
Будем строить разбиение таким образом, чтобы в результате подмножества <tex> \{B_1, B_2, ..., B_k\} </tex> оказались отсортированы в лексикографическом порядке(т.е. чтобы для любых <tex> 1 <= i < j <= k </tex> наименьший элемент <tex> B_i </tex> был меньше наименьшего элемента <tex> B_i </tex>).
