Boyer-Mooren enemmistöäänestysalgoritmi

Boyer-Mooren enemmistöäänestysalgoritmi  on algoritmi sekvenssin hallitsevan elementin löytämiseksi. N-pituisen sekvenssin hallitseva elementti on tämän sekvenssin elementti, joka esiintyy siinä enemmän kuin n/2 kertaa. Tämän algoritmin monimutkaisuus on O(n) ja tarvittava lisämuisti on O(1).

Algoritmi on nimetty R. Boyerin ja Jay Mooren mukaan, jotka julkaisivat sen vuonna 1981. [yksi]

Kuvaus

Algoritmi edellyttää kahden lisämuuttujan käyttöönottoa: ensimmäinen sisältää sekvenssin elementin, joka soveltuu parhaiten hallitsevan elementin rooliin jo tarkasteluista, ja toinen on laskuri ja on aluksi yhtä suuri kuin nolla. Algoritmi koostuu yhdestä läpikäynnistä tarkasteltavan sekvenssin läpi. Jokaisessa vaiheessa suoritetaan seuraavat toimenpiteet: jos laskurimuuttujan nykyinen arvo on nolla, tämä sekvenssin elementti kirjoitetaan ensimmäiseen muuttujaan ja laskuri on yhtä suuri kuin 1. Jos laskurin arvo on eri kuin nolla , sitten sekvenssin nykyistä elementtiä verrataan ensimmäiseen muuttujaan kirjoitettuun arvoon. Jos ne täsmäävät, laskuria kasvatetaan 1:llä, muussa tapauksessa sitä pienennetään yhdellä.

Algoritmin pseudokoodi :

Kun kaikki elementit on otettu huomioon, ensimmäinen muuttuja sisältää sekvenssin hallitsevan elementin, jos sellainen on olemassa. Jos sekvenssissä ei kuitenkaan ole tällaista elementtiä, ensimmäinen muuttuja sisältää silti jonkin sekvenssin elementin. Siksi, jos hallitsevan elementin olemassaolosta ei ole varmuutta, tulee suorittaa ylimääräinen läpikulku taulukon läpi, jotta varmistetaan, että taulukosta löydetty elementti esiintyy enemmän kuin n/2 kertaa. Jos toisen läpimenon tuloksena käy ilmi, että elementti esiintyy enintään n/2 kertaa, niin hallitsevan elementin sekvenssi ei sisällä. [2]

Muistiinpanot

  1. Boyer, RS & Moore, J S. (1991), MJRTY - nopea enemmistöäänestysalgoritmi , Boyer, RS, Automated Reasoning: Essays in Honor of Woody Bledsoe , Automated Reasoning Series, Dordrecht, Alankomaat: Kluwer Academic, Publishers Kanssa. 105–117, doi : 10.1007/978-94-011-3488-0_5 , < http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA131702 >  . Julkaistu alun perin teknisenä raportina vuonna 1981.
  2. Cormode, Graham & Hadjieleftheriou, Marios (lokakuu 2009), Usein esiintyvien kohteiden löytäminen tietovirroista , ACM: n viestintä, vol. 52 (10): 97 , DOI 10.1145/1562764.1562789  .