Algoritmus výběru

V informatice je výběrový algoritmus algoritmem pro nalezení k -tého největšího prvku v poli (takový prvek se nazývá statistika k-tého řádu ). Speciálními případy tohoto algoritmu je nalezení minimálního prvku , maximálního prvku a mediánu . Existuje algoritmus, který zaručeně vyřeší problém výběru k-tého největšího prvku v O( n ).

Výběr řazením

Problém výběru lze zredukovat na třídění . Ve skutečnosti můžete pole seřadit a pak vzít prvek, který potřebujete, v pořadí. To je účinné, když je třeba výběr provést vícekrát: pak můžete pole seřadit v O( n log n ) a poté z něj vybrat prvky. Pokud je však třeba provést volbu jednou, může být tento algoritmus nepřiměřeně dlouhý.

Lineární algoritmus pro nalezení minima (maxima)

Je zřejmé, jak najít minimum (maximum) v daném poli v lineárním čase:

Zpočátku přiřadit $min=a[0];$
Pro každý prvek spusťte: if , přiřaďte . $a[i]$ $min>a[i]$ $min=a[i]$

Průměrný lineární algoritmus pro nalezení statistiky k -tého řádu

Existuje algoritmus pro nalezení statistiky k -tého řádu založený na algoritmu rychlého třídění, který v průměru běží v O( n ).

Myšlenkou algoritmu je, že pole je rozděleno na dvě části vzhledem k náhodně (ekvipravděpodobně) vybranému prvku - prvky menší než vybraný spadají do jedné části, zbytek do druhé (tato operace se provádí pro , při na jeho konci je vybraný prvek na pozici ) . Pokud jsou v první části ( ) přesně prvky, pak je vybraný prvek požadovaný, pokud , pak se algoritmus provede rekurzivně pro první část pole, jinak - pro druhou (v druhém případě pro další iterace se odečte od ). Rekurzivní volání vedou k exponenciálnímu zmenšování velikosti zpracovávaného pole s každou iterací, az tohoto důvodu je doba provádění algoritmu . $Na)$ $j$ $k-1$ $j=k$ $j>k$ $k$ $j$ $Na)$

Algoritmus BFPRT (lineární deterministický)

BFPRT-Algorithm vám umožňuje najít statistiku k -tého řádu garantovanou v O( n ). Pojmenován po svých vynálezcích: Manual Blum, Robert W. Floyd, Vaughan R. P ratt , Ronald L. R ivest a Robert Endre T arjan. Používá se s poměrně dlouhým seznamem prvků, přes 800 prvků.

Jak to funguje

Vstup: číslo představující -tý prvek. $i$ $i$

Seznam je rozdělen na podmnožiny prvků, každá po 5 prvcích (kromě poslední podmnožiny). Počet prvků v podmnožinách může přesáhnout 5 a v každém případě musí být liché. Pokud však seznam rozdělíte na podmnožiny po 3 prvcích, doba běhu nebude lineární.
Každá podmnožina je tříděna pomocí vhodného třídícího algoritmu .
Nechť je množina mediánů vytvořených v podmnožinách po třídění. Rekurzivně najděte medián v — medián mediánů. Zavolejme jí . $S$ $S$ $s$
- Výsledná struktura po kroku 3 má následující vlastnost:
  - Čtvrtina všech prvků má stejně klíč . (Podmnožina sady ) $<s$ $S_{1}$
  - Čtvrtina všech prvků má stejně klíč . (Podmnožina sady ) $>s$ $S_{2}$
Nyní je seznam rozdělen relativně k mediánům na 2 podmnožiny a . V tomto případě je třeba s s porovnat pouze polovinu všech prvků, protože dvě čtvrtiny prvků jsou již seřazeny vzhledem k s. Výsledkem je, že každá z podmnožin a obsahuje maximálně 3/4 všech prvků (minimum je 1/4 všech prvků). $S_{1}$ $S_{2}$ $S_{1}$ $S_{2}$
Pokud:
- $i=|S_{1}|+1$ , pak je nalezen požadovaný prvek - to je medián mediánů $s$
- $i\leq |S_{1}|$ , pak je algoritmus volán rekurzivně na množině $S_{1}$
- v každém jiném případě je algoritmus volán rekurzivně na množině $S_{2}$

Garantovaná dostupnost

S každým rekurzivním voláním vám algoritmus umožňuje vyřadit alespoň čtvrtinu všech prvků. To poskytuje horní hranici zaručené lineární doby běhu pro deterministický algoritmus , protože je vyjádřena vztahem opakování . Obecně, pokud mají podmnožiny velikost , je doba běhu vyjádřena jako . $T(n)=O(n)+T\left({\frac {n}{5}}\right)+T\left({{\frac {7}{10}}n}\right )$ $2k+1$ $T(n)=O(n)+T\left({\frac {n}{2k+1}}\right)+T\left({{\frac {3k+1}{4k+2 }}n}\right)$

Literatura

Volker Heun. Základní algoritmy = Grundlegende Algorithmen. - 1. vyd. - Mnichov: Vieweg Verlag, 2000. - S. 86. - ISBN 3-528-03140-9 .
Time Bounds for Selection od Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest a Robert E. Tarjan. Journal of Computer and System Sciences 7.4. srpna 1973 , 448-460