分割統治アルゴリズムを使用して、配列内のオブジェクトの少なくとも半分が (関数で) true を返すかどうかを確認するにはどうすればよいでしょうか? オブジェクトには列挙可能な値がないため、オブジェクト A は決してオブジェクト B より大きくはありません。
明確にするために、その関数を使用してすべてのオブジェクトを互いに比較します。したがって、 funct(Obj a, Obj b) は、いくつかの基準に基づいて true または false を返します。それらはひとまとめにすることができます。比較したオブジェクトの少なくとも半分が true を返したかどうかを知りたいだけです。
分割統治法を使用する理由は何ですか? 自明なアルゴリズム「反復とカウント」を使用すると、質問に答えるとO(n)のように見えます...そして、オブジェクトの半分がO(n/2)未満のオブジェクトをチェックするアルゴリズムを使用してtrueを返すことをおそらく知ることはできません。これは O(n) と同じです。
EDIT : OK、編集は、適用している述語ではないことを示しています。したがって、私の答えは当てはまりません。「オブジェクトの半分が true を返す」を実際にどのように定義するのか、まだわかりません。それらは何と比較して true を返しますか? 私たちが持っているのはn**2ペアです（オブジェクトがそれ自体と比較できるかどうかは不明です）。n**2比較関数が適用されると、半分のペアが true を返すということですか?
もしそうなら、前のものと非常によく似た推論は、あなたは運命づけられており、それ以上のことはできないと結論付けます.O(n**2)
多くのことに依存します：
オブジェクトはいくつありますか? 彼らは注文されていますか？どの言語を使用していますか? これはどのマシンで実行されていますか?
プロセスがスレッド化の恩恵を受けるマシン上に、ランダムに並べられた多くのアイテムがある場合は、いくつかのスレッドを作成し、それぞれに作業するデータのチャンクを割り当てます。合格または不合格の数がオブジェクト数の半分を超えると、答えが得られます。