나누기 및 정복 - 비교

Question

배열의 내 개체 중 절반 이상이 나누기 및 정복 알고리즘을 사용하여 일부 기능에서 true를 반환하는 경우 어떻게 찾을 수 있습니까? 개체에는 열거 할 수있는 값이 없으므로 개체 A는 결코 개체 B보다 큽니다.

명확하게하려면 해당 함수를 사용하여 모든 개체를 서로 비교하십시오. 따라서 funct (Obj a, Obj b)는 몇 가지 기준에 따라 true 또는 false를 반환합니다. 그것들은 함께 묶일 수 있습니다. 단지 비교 대상의 절반 이상이 true를 반환했는지 알고 싶을뿐입니다.

Answer 1

많은 항목에 따라 달라집니다.

몇 개의 객체가 있습니까? 주문 했습니까? 어떤 언어를 사용하고 있습니까? 이 컴퓨터는 어떤 컴퓨터에서 실행되고 있습니까?

무작위로 많은 수의 항목이있는 경우 프로세스의 스레드가 스레드를 통해 이익을 얻고, 몇 개의 스레드를 만들고 각각에 작업 할 데이터 덩어리를 할당한다고 말하고 싶습니다. 패스 수를 얻거나 객체 수의 반 이상을 실패하면 대답을 얻을 수 있습니다.

Answer 2

왜 나누고 정복 하시겠습니까? 당신의 질문에 답하는 것은 간단한 알고리즘 'iterate and count'를 사용할 때 O (n) 인 것처럼 보이며 O (n/2) 객체보다 적은 알고리즘을 사용하여 객체의 절반이 true를 반환한다는 것을 알 수는 없습니다. 이는 O (n)과 동일하다.

편집 : 확인을 클릭하면 적용 대상이 아닌 것으로 나타납니다. 그래서 내 대답은 적용되지 않습니다. 나는 여전히 당신이 정말로 '반 객체가 사실로 돌아가는'것을 어떻게 정의하는지 이해하지 못합니다. 그들은 무엇에 비해 사실로 돌아 옵니까? 우리가 가지고있는 것은 n**2 쌍입니다 (어쩌면 개체가 자체와 비교 될 수 있는지는 불분명합니다). 비교 기능이 적용될 때 n**2 쌍 중 절반이 true를 반환한다는 것을 의미합니까? 그래서 이전과 매우 유사한 추론 당신이 운명 체결하고 할 수없는 경우

보다 나은 O(n**2)