Boyer–Moore majority vote algorithm (original) (raw)
Алгоритм большинства голосов Бойера — Мура — это алгоритм для нахождения преобладающего элемента последовательности. Преобладающим элементом последовательности длины n называется такой элемент этой последовательности, который встречается в ней более чем n/2 раз. Сложность данного алгоритма O(n), а требуемая дополнительная память — O(1). Алгоритм назван в честь и , опубликовавших его в 1981 году.
| Property | Value |
|---|---|
| dbo:abstract | The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. It is named after Robert S. Boyer and J Strother Moore, who published it in 1981, and is a prototypical example of a streaming algorithm. In its simplest form, the algorithm finds a majority element, if there is one: that is, an element that occurs repeatedly for more than half of the elements of the input.A version of the algorithm that makes a second pass through the data can be used to verify that the element found in the first pass really is a majority. If a second pass is not performed and there is no majority the algorithm will not detect that no majority exists. In the case that no strict majority exists, the returned element can be arbitrary; it is not guaranteed to be the element that occurs most often (the mode of the sequence).It is not possible for a streaming algorithm to find the most frequent element in less than linear space, for sequences whose number of repetitions can be small. (en) Алгоритм большинства голосов Бойера — Мура — это алгоритм для нахождения преобладающего элемента последовательности. Преобладающим элементом последовательности длины n называется такой элемент этой последовательности, который встречается в ней более чем n/2 раз. Сложность данного алгоритма O(n), а требуемая дополнительная память — O(1). Алгоритм назван в честь и , опубликовавших его в 1981 году. (ru) 博耶-摩尔多数投票算法（英語：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由和在1981年发表，也是的一种典型算法。 这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Boyer-Moore_MJRTY.svg?width=300 |
| dbo:wikiPageID | 44847034 (xsd:integer) |
| dbo:wikiPageLength | 7130 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112657224 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Element_distinctness_problem dbr:Binary_logarithm dbr:Bit_complexity dbr:Algorithm dbr:Analysis_of_algorithms dbc:Streaming_algorithms dbr:Misra–Gries_heavy_hitters_algorithm dbr:Mode_(statistics) dbr:Linear_time dbr:Majority_function dbr:Majority_problem_(cellular_automaton) dbr:Local_variable dbr:Cellular_automaton dbr:J_Strother_Moore dbr:Misra–Gries_summary dbr:Random-access_machine dbr:Robert_S._Boyer dbr:Majority dbr:Turing_machine dbr:Streaming_algorithm dbr:Pseudocode dbr:Boolean_value dbr:Machine_word dbr:File:Boyer-Moore_MJRTY.svg |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Streaming_algorithms |
| rdfs:comment | Алгоритм большинства голосов Бойера — Мура — это алгоритм для нахождения преобладающего элемента последовательности. Преобладающим элементом последовательности длины n называется такой элемент этой последовательности, который встречается в ней более чем n/2 раз. Сложность данного алгоритма O(n), а требуемая дополнительная память — O(1). Алгоритм назван в честь и , опубликовавших его в 1981 году. (ru) 博耶-摩尔多数投票算法（英語：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由和在1981年发表，也是的一种典型算法。 这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。 (zh) The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. It is named after Robert S. Boyer and J Strother Moore, who published it in 1981, and is a prototypical example of a streaming algorithm. (en) |
| rdfs:label | Boyer–Moore majority vote algorithm (en) Алгоритм большинства голосов Бойера — Мура (ru) 多数投票算法 (zh) |
| owl:sameAs | freebase:Boyer–Moore majority vote algorithm wikidata:Boyer–Moore majority vote algorithm dbpedia-ru:Boyer–Moore majority vote algorithm dbpedia-sr:Boyer–Moore majority vote algorithm dbpedia-zh:Boyer–Moore majority vote algorithm https://global.dbpedia.org/id/ouU9 |
| prov:wasDerivedFrom | wikipedia-en:Boyer–Moore_majority_vote_algorithm?oldid=1112657224&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Boyer-Moore_MJRTY.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Boyer–Moore_majority_vote_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Boyer–Moore |
| is dbo:wikiPageRedirects of | dbr:Boyer-Moore_Majority_Vote_Algorithm dbr:Boyer-Moore_majority_vote_algorithm dbr:Moore's_voting_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Boyer-Moore_Majority_Vote_Algorithm dbr:Boyer–Moore dbr:Boyer-Moore_majority_vote_algorithm dbr:Misra–Gries_heavy_hitters_algorithm dbr:Range_query_(data_structures) dbr:Majority_function dbr:J_Strother_Moore dbr:Misra–Gries_summary dbr:Robert_S._Boyer dbr:Streaming_algorithm dbr:Moore's_voting_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Boyer–Moore_majority_vote_algorithm |
