n个对象的等价测试

假设我们给了'n'个对象和一个接受两个输入的子例程，并说它们是否相等（例如，如果它们相等，它可以给出输出为1）。n个对象的等价测试

我需要想出一个算法，它调用上述函数O（n log n）次并决定输入是否有多于'n/2'的项目彼此等效。

2014-10-02 cardamom

'为O（n log n）的'通常暗示朝向以某种方式排序。这个子程序真的只是为了等于还是比较两个，所以你可以使用它来进行排序？ – Sirko 2014-10-02 09:23:19

有一个解决方案需要O（n）比较。 – 2014-10-02 11:46:13

这里是一个经典的分而治之溶液其给出为O（n log n）的

分裂成两个子集，A1和A2，...，并显示T（N）是O（n log n）的。如果A具有多数元素v，则v也必须是A1或A2的多数元素或两者。等价的反向正面重述是立即的:(如果v是< =每个是一半，那么它是< =总数的一半）。如果两个部分具有相同的多数元素，则它自动成为A的主要元素。如果的部分有一个多数元素，计算两个部分中该元素的重复次数（在O（n）时间）以查看它是否是多数元素。如果两部分都有多数，你可能需要为这两个候选人中的每一个做这个计数，仍然是O（n）。这种分割可以递归地完成。基本情况是当n = 1时。一个递归关系是T（n）= 2T（n/2）+ O（n），所以T（n）是O（n log n）。

http://anh.cs.luc.edu/363/handouts/MajorityProblem.pdf

来源

2014-10-24 06:21:44 cardamom

-2

考虑到序列是有序的，你可以使用binary search，这需要O(log n)，因为你必须做的每一个元素，你必须n元素将采取O(n*log n)。

来源

2014-10-02 11:32:05

比较器似乎没有提供订购信息。 – 2014-10-02 14:14:53

什么比较器？ “ – 2014-10-02 14:25:17

”子程序需要两个输入，并说他们是否等价“ – 2014-10-02 14:25:33

您可以使用Boyer-Moore多数票表决算法，它最多可以进行n-1次比较。

function find_majority(A) 
    majority = None 
    count = 0 
    for a in A: 
     if count == 0 
      majority = a 
     else if a == majority 
      count += 1 
     else 
      count -= 1 
    return majority

如果在数组中出现超过n/2次，它将返回最常见的元素。

如果您需要知道是否有是多数项目，那么您可以再次通过数组，计算从find_majority函数返回的值的次数。这又增加了n个比较。

来源

2014-10-02 11:42:51

n个对象的等价测试

回答

相关问题