Divide and Conquer - Сравнить

Question

Как я могу найти, если хотя бы половина моих объектов в массиве вернет true (по некоторой функции), используя алгоритм деления и покорения? Объекты не имеют перечислимого значения, поэтому объект A отнюдь не больше объекта B.

Чтобы прояснить, сравнивая все объекты друг с другом с помощью этой функции. Так funct (Obj a, Obj b) возвращает true или false, основываясь на некоторых критериях. Они могут быть сгруппированы вместе, мы просто хотим знать, вернулась ли по крайней мере половина сравниваемых объектов.

Answer 1

Зависит от многих вещей:

Сколько объектов есть? Заказываются ли они? На каком языке вы используете? Какая машина работает?

Я бы сказал, что если у вас есть много предметов, случайно упорядоченных, на машине, процессы которого выиграют от потоковой обработки, создадут несколько потоков и назначат каждому из них кусок данных для работы. Как только вы получите количество проходов или не получится больше половины количества объектов, вы получите ответ.

Answer 2

Почему вы хотите использовать разделение и побеждать? Ответ на ваш вопрос выглядит как O (n) при использовании тривиального алгоритма «итерация и подсчет» ... и вы не можете знать, что половина объектов вернет true, используя любой алгоритм, проверяющий объекты меньше O (n/2) что совпадает с O (n).

EDIT: ОК, редактирование показывает, что это не предикат, который вы применяете. Поэтому мой ответ не применяется. Я все еще не понимаю, как вы действительно определяете «половина объекта return true». Они возвращают истину по сравнению с чем? У нас есть n**2 пары (может быть, меньше, неясно, можно ли сравнить объект с собой). Вы имеете в виду, что пара n**2 возвращает true при использовании функции сравнения?

Если так рассуждения очень похожи на предыдущий заключит вы обречены и не может сделать лучше, чем O(n**2)