n个对象的equalence测试 [英] equalence 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为＆lt; =一半在每个，它为＆lt; =一半在总量）如果两个部分具有相同的多数的元素，它是自动为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个对象的equalence测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！