Алгоритм разбиения массива на подмножества с минимальной суммарной дисперсией
У меня есть массив чисел с плавающей запятой, и я хотел бы разбить массив на два подмножества, чтобы их общая дисперсия была минимизирована.
Общая дисперсия определяется следующим образом:
var = (var_1 * n_1 + var_2 * n_2)/(n_1 + n_2)
где n_1 а также n_2 количество элементов слева / справа соответственно, и var_1 а также var_2 дисперсия слева / справа соответственно.
Мой вопрос: есть ли эффективный алгоритм для нахождения глобального минимума полной дисперсии? Алгоритм должен вывести два подмножества, каждое из которых содержит элементы соответствующей группы.
Кроме того, предположим, что каждый элемент является кортежем (x,y)и вместо дисперсии я хотел бы найти глобальную ковариацию слева и справа, определенную так же, как и выше. Есть ли какой-то общий алгоритм для решения таких проблем с разделами? Я думаю, это должно быть сложнее, потому что все алгоритмы, которые я могу придумать, требуют сортировки массива, но здесь нет очевидного компаратора для сортировки кортежа.