n个对象的等效测试 [英] Equivalence testing of n objects

问题描述

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

Assume that we are given 'n' objects and a subroutine that takes two inputs and says if they are equivalent or not (e.g. it can give output as 1 if they are equal).

我需要提出一种算法，该算法调用上述函数O（n log n）次，并确定输入中是否包含大于等于'n / 2'个项目。

I need to come up with an algorithm that calls the above function O(n log n) times and decides if the input has more than 'n/2' items that are equivalent to each other.

推荐答案

这是经典的分而治之方案，给出O（n log n）

Here is a classical divide and conquer solution which gives 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）。

split into two subsets, A1 and A2, ..., and show T(n) is O(n log n). If A has a majority element v, v must also be a majority element of A1 or A2 or both. The equivalent contra-positive restatement is immediate: (If v is <= half in each, it is <= half in the total.) If both parts have the same majority element, it is automatically the majority element for A. If one of the parts has a majority element, count the number of repetitions of that element in both parts (in O(n) time) to see if it is a majority element. If both parts have a majority, you may need to do this count for each of the two candidates, still O(n). This splitting can be done recursively. The base case is when n = 1. A recurrence relation is T(n) = 2T(n/2) + O(n), so T(n) is O(n log n) by the Master Theorem.

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

这篇关于n个对象的等效测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！