n个对象的等价性测试

Question

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

我需要提出一种算法，该算法调用上述函数O（n log n）次，并确定输入是否具有多于彼此等效的'n / 2'项。

Answer 1

您可以使用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个比较。

Answer 2

这是一个经典的分而治之的解决方案，它给出了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

Answer 3

保罗汉金的答案是$\mathcal{O}(n)$解决方案，非常花哨。

如果不使用Boyer-Moore，我们也可以在$\mathcal{O}(nlogn)$中解决这个问题。每次比较之后，我们“掉落”不同的一对牌并将同等的“合并”成一组，依此类推，每次我们丢弃相同数量的牌时，最后的左卡或卡组是“多数” “那么我们可以再次运行比较来检查卡是否为真。

每当我们下降时，我们至少会丢弃多数卡和另一张卡，因此它不会影响结果，丢弃过程是一个“偏移”操作。无论是丢弃还是合并，帮助我们减少至少一半的卡。所以递归时间是$logn$，总时间是$nlogn$。

Answer 4

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