Udvælgelsesalgoritme

I datalogi er en udvælgelsesalgoritme en algoritme til at finde det k . største element i en matrix (sådan et element kaldes kth ordens statistik ). Særlige tilfælde af denne algoritme er at finde minimumselementet , maksimumelementet og medianen . Der findes en algoritme, der med garanti løser problemet med at vælge det k. største element i O( n ).

Valg ved at sortere

Udvælgelsesproblemet kan reduceres til sortering . Faktisk kan du sortere et array og derefter tage det element, du har brug for, i rækkefølge. Dette er effektivt, når valget skal foretages flere gange: så kan du sortere arrayet i O( n log n ) og derefter vælge elementer fra det. Men hvis valget skal træffes én gang, kan denne algoritme være urimelig lang.

Lineær algoritme til at finde minimum (maksimum)

Det er klart, hvordan man finder minimum (maksimum) i en given matrix i lineær tid:

Tildel i første omgang $min=a[0];$
For hvert element skal du udføre: if , assign . $en[i]$ $min>a[i]$ $min=a[i]$

En gennemsnitlig lineær algoritme til at finde k -te ordens statistik

Der er en algoritme til at finde k -te ordens statistik baseret på quicksort algoritmen , der kører i O( n ) i gennemsnit.

Ideen med algoritmen er, at arrayet er opdelt i to dele i forhold til et tilfældigt (med ligeså sandsynligt) udvalgt element - elementer, der er mindre end det valgte, falder i den ene del, resten i den anden (denne operation udføres for , kl. i slutningen af det er det valgte element på plads ). Hvis der er nøjagtige elementer i den første del ( ), så er det valgte element det ønskede element, hvis , så udføres algoritmen rekursivt for den første del af arrayet, ellers - for den anden (i sidstnævnte tilfælde for næste iteration, trækkes fra ). Rekursive kald fører til en eksponentielt faldende størrelse af det behandlede array med hver iteration, og af denne grund er eksekveringstiden for algoritmen . $På)$ $j$ $k-1$ $j=k$ $j>k$ $k$ $j$ $På)$

BFPRT-algoritme (lineær deterministisk)

BFPRT-algoritme giver dig mulighed for at finde k - te ordens statistik garanteret i O( n ). Opkaldt efter dets opfindere: Manual Blum, Robert W. Floyd, Vaughan R. P ratt , Ronald L. R ivest og Robert Endre T arjan. Det bruges med en ret lang liste af elementer, over 800 elementer.

Sådan virker det

Input: tal, der repræsenterer det -th element. $jeg$ $jeg$

Listen er opdelt i delmængder af elementer, 5 elementer hver (undtagen den sidste delmængde). Antallet af elementer i delmængder kan overstige 5 og skal under alle omstændigheder være ulige. Men hvis du opdeler listen i undersæt af 3 elementer, vil køretiden ikke være lineær.
Hvert delsæt sorteres ved hjælp af en passende sorteringsalgoritme .
Lade være sættet af medianer dannet i delmængder efter sortering. Find rekursivt medianen i - medianen af medianer. Lad os ringe til hende . $S$ $S$ $s$
- Den resulterende struktur efter trin 3 har følgende egenskab:
  - En fjerdedel af alle elementer har alligevel en nøgle . (En delmængde af sættet ) $<s$ $S_{1}$
  - En fjerdedel af alle elementer har alligevel en nøgle . (En delmængde af sættet ) $>s$ $S_{2}$
Nu er listen opdelt i forhold til medianen s i 2 delmængder og . I dette tilfælde skal kun halvdelen af alle elementer sammenlignes med s, da to fjerdedele af elementerne allerede er sorteret i forhold til s. Som følge heraf indeholder hver af delmængderne og maksimalt 3/4 af alle elementer (minimum er 1/4 af alle elementer). $S_{1}$ $S_{2}$ $S_{1}$ $S_{2}$
Hvis en:
- $i=|S_{1}|+1$ , så findes det ønskede element - dette er medianen af medianerne $s$
- $i\leq |S_{1}|$ , så kaldes algoritmen rekursivt på sættet $S_{1}$
- i alle andre tilfælde kaldes algoritmen rekursivt på sættet $S_{2}$

Garanteret oppetid

Med hvert rekursivt opkald giver algoritmen dig mulighed for at kassere mindst en fjerdedel af alle elementer. Dette giver en øvre grænse for den garanterede lineære køretid for en deterministisk algoritme , da den er udtrykt ved gentagelsesrelationen . Generelt, hvis undersættene er af størrelse , udtrykkes køretiden som . $T(n)=O(n)+T\venstre({\frac {n}{5}}\right)+T\left({{\frac {7}{10}}n}\right )$ $2k+1$ $T(n)=O(n)+T\venstre({\frac {n}{2k+1}}\right)+T\venstre({{\frac {3k+1}{4k+2 }}n}\right)$

Litteratur

Volker Heun. Grundlæggende Algoritmer = Grundlegende Algoritmer. - 1. udg. - München: Vieweg Verlag, 2000. - S. 86. - ISBN 3-528-03140-9 .
Time Bounds for Selection af Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest og Robert E. Tarjan. Journal of Computer and System Sciences 7.4. august 1973 , 448-460