分而治之 - 比較

如何使用分而治之算法來查找數組中的至少一半對象是否返回true（在某些函數上）？這些對象沒有可枚舉的值，因此對象A絕不會大於對象B.分而治之 - 比較

要澄清，使用該函數將所有對象相互比較。所以功能（Obj a，Obj b）根據一些標準返回true或false。它們可以組合在一起，我們只是想知道至少一半的比較對象是否回覆真實。

2010-12-08 blahhhhhh

是將爲該函數成羣一起返回true的人？ – 2010-12-08 21:05:58

澄清，使用該函數將所有對象相互比較。所以功能（Obj a，Obj b）根據一些標準返回true或false。它們可以組合在一起，我們只是想知道至少一半的比較對象是否回覆真實。 – blahhhhhh 2010-12-08 21:09:10

是否想要將所有要素對進行比較，還是將數組的所有要素與已知值進行比較，例如：如果該數組是整數，並且您想知道是否有一半是單個數字？ – 2010-12-08 21:17:54

取決於很多事情：

多少對象有哪些？他們訂購了嗎？您使用哪種語言？這臺機器運行什麼機器？

我想說，如果你有很多項目，隨機排序，在一個機器誰是進程將受益於線程，創建一些線程和分配每一個數據塊的工作。一旦獲得通過次數或失敗的次數超過對象數量的一半，就得到了答案。

2010-12-08 21:11:05 MStodd

爲什麼要使用分而治之？在使用簡單算法'迭代和計數'時，回答你的問題看起來是O（n）...並且你不可能知道一半的對象會使用任何檢查少於O（n/2）對象的算法返回真，這與O（n）相同。

編輯：好的，編輯顯示它不是您正在應用的謂詞。所以我的答案不適用。我仍然不明白你如何真正定義'一半對象返回true'。與什麼相比，他們會迴歸真實？我們擁有的是n**2對（可能更少，不清楚對象是否可以與自身進行比較）。您是否認爲在應用比較函數時，n**2對的一半返回true？

如果這樣推理非常相似，前一個將結束你註定不能做比O(n**2)

2010-12-08 21:15:59 kriss

回答