Element distinctness problem: Difference between revisions

Revision as of 21:15, 20 July 2013

Revision as of 21:17, 20 July 2013

Line 56:

Elements that occur more than ''n''/''k'' times in a multiset of size n may be found in time O(''n'' log ''k''). The element distinctness problem is a special case of ''k''=''n''. This algorithm is optimal under the [[decision tree model]] of computation.<ref>{{citation|first1=J.|last1=Misra|first2=D.|last2=Gries|author2-link=David Gries|title=Finding repeated elements|journal=Science of Computer Programming|volume=2|year=1982|pages=143–152}}.</ref>

The algorithm is a generalization of the one for a special case of ''k''=2, which had a rather convoluted history of publication.<ref name=bm>{{citation|first1=R. S.|last1=Boyer|author1=-link=Robert S. Boyer|first2=J S.|last2=Moore|author2-link=J Strother Moore|contribution=MJRTY - A Fast Majority Vote Algorithm|editor-first=R. S.|editor-last=Boyer|title=Automated Reasoning: Essays in Honor of Woody Bledsoe|series=Automated Reasoning Series|publisher=Kluwer Academic Publishers|___location=Dordrecht, The Netherlands|year=1991|pages=105–117}}.</ref>

The above algorithms rely only on the test of identity of the elements. If sorting is allowed, previously known [[order statistics]] finding algorithms may be exploited. For example, for ''k''=2, a [[median]] may be found first in [[linear time]], and then it may be easily tested whether there are more than ''n''/2 median elements. However the above algorithms require fewer comparisons than the order statistics algorithms.<ref name=bm/>