Diviser et Conquer - Comparer

Question

Comment serais-je capable de trouver si au moins la moitié de mes objets dans un tableau retournent vrai (sur une fonction) en utilisant un algorithme de division et de conquête? Les objets n'ont pas de valeur énumérable, donc l'objet A n'est pas plus grand que l'objet B.

Pour clarifier, comparer tous les objets les uns aux autres en utilisant cette fonction. Donc funct (Obj a, Obj b) renvoie vrai ou faux selon certains critères. Ils peuvent être groupés ensemble, nous voulons juste savoir si au moins la moitié des objets comparés est vrai.

Answer 1

Dépend beaucoup de choses:

Combien d'objets sont là? Sont-ils commandés? Quelle langue utilisez-vous? Sur quelle machine est-ce que cela fonctionne?

Je dirais que si vous avez beaucoup d'éléments, commandés au hasard, sur une machine dont les processus bénéficieraient de l'enfilage, créez quelques threads et attribuez à chacun un morceau de données pour travailler avec. Une fois que vous obtenez le nombre de passes ou échoue plus de la moitié du nombre d'objets, vous avez votre réponse.

Answer 2

Pourquoi voudriez-vous utiliser diviser pour régner? Répondre à votre question semble être O (n) lors de l'utilisation de l'algorithme trivial 'itérer et compter' ... et vous ne pouvez pas connaître la moitié des objets retournera vrai en utilisant un algorithme vérifiant moins de O (n/2) objets, qui est le même que O (n).

EDIT: OK, l'édition montre que ce n'est pas un prédicat que vous appliquez. Donc, ma réponse ne s'applique pas. Je ne comprends toujours pas comment vous définissez réellement 'la moitié de l'objet retourne vrai'. Ils reviennent vrai par rapport à quoi? Ce que nous avons est n**2 paires (peut-être moins, on ne sait pas si un objet peut être comparé à lui-même). Voulez-vous dire que la moitié des paires n**2 retournent vrai lorsque la fonction de comparaison est appliquée?

Si donc un raisonnement très semblable à la précédente vous conclure êtes condamné et ne peut faire mieux que O(n**2)