Divide and Conquer - Vergleichen

Question

Wie würde ich finden können, wenn mindestens die Hälfte meiner Objekte in einem Array wahr (in einer Funktion) mit einem Divide and Conquer-Algorithmus zurückgibt? Die Objekte haben keinen aufzählbaren Wert, daher ist Objekt A keinesfalls größer als Objekt B.

Um zu verdeutlichen, alle Objekte miteinander zu vergleichen, die diese Funktion verwenden. So gibt funct (Obj a, Obj b) basierend auf einigen Kriterien wahr oder falsch zurück. Sie können zusammengelegt werden, wir wollen nur wissen, ob mindestens die Hälfte der verglichenen Objekte wahr ist.

Answer 1

hängt von einer Menge Dinge:

Wie viele Objekte gibt es? Sind sie bestellt? Welche Sprache benutzen Sie? Auf welcher Maschine läuft das?

Ich würde sagen, wenn Sie eine Menge von Elementen haben, nach dem Zufallsprinzip geordnet, auf einer Maschine, deren Prozesse von Threading profitieren würden, erstellen Sie ein paar Threads und weisen Sie jedem ein Stück Daten zu arbeiten. Sobald Sie die Anzahl der Durchgänge erhalten haben oder mehr als die Hälfte der Anzahl der Objekte ausfällt, haben Sie Ihre Antwort.

Answer 2

Warum möchten Sie Divide and Conquer verwenden? Beantworten Sie Ihre Frage als O (n), wenn Sie den trivialen Algorithmus 'iterate and count' verwenden ... und Sie nicht wissen können, dass die Hälfte der Objekte wahr ist, indem Sie einen Algorithmus verwenden, der weniger als O (n/2) Objekte prüft, Das ist das gleiche wie O (n).

BEARBEITEN: OK, die Bearbeitung zeigt, dass es kein Prädikat ist, das Sie anwenden. Also meine Antwort gilt nicht. Ich verstehe immer noch nicht, wie Sie wirklich 'die Hälfte des Objekts als wahr' definieren. Sie kehren wahr im Vergleich zu was zurück? Was wir haben, ist n**2 Paare (vielleicht weniger, ist es unklar, ob ein Objekt mit sich selbst verglichen werden kann). Meinst du die Hälfte der n**2 Paare geben wahr, wenn Vergleichsfunktion angewendet wird?

Wenn so eine Argumentation sehr ähnlich wie die vorherigen zu dem Schluss kommen Sie zum Scheitern verurteilt sind, und kann nicht besser als O(n**2)