Valintaalgoritmi

Tietojenkäsittelytieteessä valintaalgoritmi on algoritmi , jolla löydetään taulukon k : nneksi suurin elementti (tällaista elementtiä kutsutaan k:nnen kertaluvun tilastoksi ). Tämän algoritmin erikoistapauksia ovat minimielementin , maksimielementin ja mediaanin löytäminen . On olemassa algoritmi, joka taatusti ratkaisee ongelman valita k:nneksi suurin elementti O( n :ssä ).

Valinta lajittelemalla

Valintaongelma voidaan supistaa lajitteluun . Todellakin, voit lajitella taulukon ja ottaa sitten tarvitsemasi elementin järjestyksessä. Tämä on tehokasta, kun valinta on tehtävä useita kertoja: sitten voit lajitella taulukon O( n log n ) -muodossa ja valita siitä elementtejä. Jos valinta on kuitenkin tehtävä kerran, tämä algoritmi voi olla kohtuuttoman pitkä.

Lineaarinen algoritmi minimin (maksimi) löytämiseksi

Ilmeisesti kuinka löytää minimi (maksimi) tietystä taulukosta lineaarisessa ajassa:

Määritä aluksi $min = a[0];$
Suorita jokaiselle elementille : if , assign . $a[i]$ $min>a[i]$ $min=a[i]$

Keskimääräinen lineaarinen algoritmi k : nnen kertaluvun tilaston löytämiseksi

K :nnen kertaluvun tilaston löytämiseksi on algoritmi, joka perustuu pikalajittelualgoritmiin, joka suoritetaan keskimäärin O( n ):ssa.

Algoritmin idea on, että matriisi jaetaan kahteen osaan suhteessa satunnaisesti (todennäköisesti) valittuun elementtiin - valittua pienemmät elementit putoavat yhteen osaan, loput toiseen (tämä toiminto suoritetaan , klo. sen lopussa valittu elementti on paikallaan ) . Jos ensimmäisessä osassa ( ) on täsmälleen elementtejä, niin valittu elementti on haluttu, jos , niin algoritmi suoritetaan rekursiivisesti taulukon ensimmäiselle osalle, muuten - toiselle (jälkimmäisessä tapauksessa seuraava iteraatio, vähennetään arvosta ). Rekursiiviset kutsut johtavat eksponentiaalisesti pienenevään käsitellyn taulukon kokoon jokaisella iteraatiolla, ja tästä syystä algoritmin suoritusaika on . $Päällä)$ $j$ $k-1$ $j=k$ $j>k$ $k$ $j$ $Päällä)$

BFPRT-algoritmi (lineaarinen deterministinen)

BFPRT-algoritmin avulla voit löytää k : nnen asteen tilastot, jotka on taattu O( n :ssä ). Nimetty sen keksijöiden mukaan: Manual Blum, Robert W. Floyd, Vaughan R. P ratt , Ronald L. R ivest ja Robert Endre T arjan. Sitä käytetään melko pitkällä elementtiluettelolla, yli 800 elementillä.

Kuinka se toimii

Syöte: numero , joka edustaa -:nnettä elementtiä. $i$ $i$

Luettelo on jaettu elementtien osajoukkoon, joissa kussakin on 5 elementtiä (viimeistä osajoukkoa lukuun ottamatta). Osajoukkojen elementtien lukumäärä voi ylittää 5, ja sen on joka tapauksessa oltava pariton. Jos kuitenkin jaat luettelon 3 elementin osajoukkoon, suoritusaika ei ole lineaarinen.
Jokainen osajoukko lajitellaan käyttämällä sopivaa lajittelualgoritmia .
Antaa olla joukko mediaaneja muodostettu osajoukkoja lajittelun jälkeen. Etsi rekursiivisesti mediaani mediaaneista — mediaani. Soitetaan hänelle . $S$ $S$ $s$
- Tuloksena olevalla rakenteella vaiheen 3 jälkeen on seuraava ominaisuus:
  - Neljänneksellä kaikista elementeistä on joka tapauksessa avain . (joukon osajoukko ) $<s$ $S_{1}$
  - Neljänneksellä kaikista elementeistä on joka tapauksessa avain . (joukon osajoukko ) $>s$ $S_{2}$
Nyt luettelo on jaettu suhteessa mediaaniin 2 osajoukkoon ja . Tässä tapauksessa vain puolta kaikista elementeistä on verrattava s:ään, koska kaksi neljäsosaa elementeistä on jo lajiteltu suhteessa s:ään. Tämän seurauksena jokainen osajoukko ja sisältää enintään 3/4 kaikista elementeistä (minimi on 1/4 kaikista elementeistä). $S_{1}$ $S_{2}$ $S_{1}$ $S_{2}$
Jos:
- $i=|S_{1}|+1$ , sitten löydetään haluttu elementti - tämä on mediaanien mediaani $s$
- $i\leq |S_{1}|$ , silloin algoritmia kutsutaan rekursiivisesti joukkoon $S_{1}$
- kaikissa muissa tapauksissa algoritmia kutsutaan rekursiivisesti joukkoon $S_{2}$

Taattu käyttöaika

Jokaisella rekursiivisella kutsulla algoritmi sallii sinun hylätä vähintään neljänneksen kaikista elementeistä. Tämä tarjoaa ylärajan taatulle lineaariselle käyntiajalle deterministiselle algoritmille , koska se ilmaistaan toistuvuussuhteella . Yleensä, jos osajoukot ovat kooltaan , ajoaika ilmaistaan muodossa . $T(n)=O(n)+T\left({\frac {n}{5}}\right)+T\left({{\frac {7}{10}}n}\oikea )$ $2k+1$ $T(n)=O(n)+T\left({\frac {n}{2k+1}}\right)+T\left({{\frac {3k+1}{4k+2 }}n}\oikea)$

Kirjallisuus

Volker Heun. Perusalgoritmit = Grundlegende Algorithmen. - 1. painos - München: Vieweg Verlag, 2000. - S. 86. - ISBN 3-528-03140-9 .
Aikarajat valinnalle: Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest ja Robert E. Tarjan. Journal of Computer and System Sciences 7.4 elokuu 1973 , 448-460