分而治之 - 比较
我如何才能使用分而治之算法找到数组中至少一半的对象是否返回 true（在某些函数上）？这些对象没有可枚举的值，因此对象 A 绝不大于对象 B。
为了澄清，使用该函数将所有对象相互比较。因此 funct(Obj a, Obj b) 根据某些条件返回 true 或 false。它们可以聚集在一起，我们只想知道是否至少有一半的比较对象返回 true。
How would I be able to find if at least half of my objects in an array return true (on some function) using a divide and conquer algorithm? The objects have no enumerable value, thus object A is by no means greater than object B.
To clarify, comparing all objects to each other using that function. So funct(Obj a, Obj b) returns true or false based on some criteria. They can be clumped together, we just want to know whether at least half of the compared objects returned true.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
为什么要使用分而治之的方法？当使用简单的算法“迭代和计数”时，回答你的问题看起来是 O(n) ...并且你不可能知道使用任何检查小于 O(n/2) 对象的算法会返回 true，这与 O(n) 相同。
编辑：好的，编辑显示它不是您正在应用的谓词。所以我的回答不适用。我仍然不明白你如何真正定义“一半对象返回 true”。他们返回 true 相比什么？我们拥有的是
n**2对（可能更少，不清楚一个对象是否可以与自身进行比较）。您的意思是应用比较函数时，有一半的n**2对返回 true 吗？如果是这样，与前一个非常相似的推理将得出结论，你注定要失败，并且不能做得比
O(n**2)更好。Why would you want to use divide and conquer ? Answering your question looks to be O(n) when using trivial algorithm 'iterate and count'... and you can't possibly know half of the objects will return true using any algorithm checking less than O(n/2) objects, which is the same as O(n).
EDIT: OK, the edit shows it's not a predicate you're applying. So my answer does not apply. I still does not understand how you really define 'half the object return true'. They return true compared to what ? What we have is
n**2pairs (maybe less, it is unclear if an object can be compared to itself). Do you mean half then**2pairs return true when comparison function is applied ?If so a reasoning very similar to the previous one will conclude you are doomed and can't do better than
O(n**2)取决于很多事情：
有多少个对象？
他们被命令了吗？
您使用什么语言？
这是在什么机器上运行的？
我想说，如果您在一台机器上有很多随机排序的项目，而该机器的进程将从线程中受益，则创建一些线程并为每个线程分配一块要处理的数据。一旦您获得的通过或失败数量超过对象数量的一半，您就得到了答案。
Depends on a lot of things:
How many objects are there?
Are they ordered?
What language are you using?
What machine is this running on?
I'd say that if you have a lot of items, randomly ordered, on a machine who's processes would benefit from threading, create a few threads and assign each one a chunk of data to work with. Once you get the number of passes or fails greater than half the number of objects, you have your answer.