Разделяй и властвуй - Сравните

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

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