Content deleted Content added
m WP:CHECKWIKI error fixes using AWB (10093) |
m →Generalization: Finding repeated elements: Added 1 doi to a journal cite using AWB (10213) |
||
Line 54:
==Generalization: Finding repeated elements==
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|doi=10.1016/0167-6423(82)90012-0}}.</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>
| |||