algorithm - 分而治之 - 比较

Question

如果使用分而治之算法，我如何能够找到数组中至少一半的对象是否返回 true（在某些函数上）？对象没有可枚举的值，因此对象 A 绝不大于对象 B。

为了澄清，使用该功能将所有对象相互比较。所以 funct(Obj a, Obj b) 根据某些标准返回真或假。它们可以聚集在一起，我们只想知道是否至少有一半的比较对象返回 true。

Answer 1

为什么要使用分而治之？当使用简单的算法“迭代和计数”时，回答你的问题看起来是 O(n) ......而且你不可能知道一半的对象将使用任何检查小于 O(n/2) 个对象的算法返回 true，这与 O(n) 相同。

编辑：好的，编辑显示它不是您正在应用的谓词。所以我的回答不适用。我仍然不明白您如何真正定义“对象的一半返回真”。它们与什么相比返回真实？我们所拥有的是n**2对（可能更少，不清楚一个对象是否可以与自身进行比较）。你的意思n**2是应用比较函数时有一半的对返回 true 吗？

如果是这样，与前一个非常相似的推理将得出结论，您注定要失败并且不能做得更好O(n**2)

Answer 2

取决于很多事情：

有多少物体？他们被订购了吗？您使用什么语言？这是在什么机器上运行的？

我会说，如果您在一台机器上有很多随机排序的项目，而该机器的进程将从线程中受益，请创建几个线程并为每个线程分配一块数据以供使用。一旦你得到的通过或失败的数量超过对象数量的一半，你就有了答案。