Statystyka pozycyjna

k-ta statystyka pozycyjna (ang. order statistic) – w statystyce, k-ty najmniejszy element w zbiorze, np. w próbie statystycznej. Inaczej element, który w posortowanym niemalejąco ciągu elementów zbioru znalazłby się na k-tej pozycji^[1].

W zbiorze ${\displaystyle n}$-elementowym pierwszą statystyką pozycyjną (${\displaystyle k=1}$) jest jego minimum, a ${\displaystyle n}$-tą statystyką pozycyjną – maksimum w tym zbiorze. Jeśli ${\displaystyle n}$ jest nieparzyste, mediana w tym zbiorze to ${\displaystyle \textstyle (n+1)/2}$-sza statystyka pozycyjna. W przeciwnym wypadku zbiór ma dwie mediany: dolną i górną, którymi są odpowiednio ${\displaystyle \textstyle \left\lfloor (n+1)/2\right\rfloor }$-sza i ${\displaystyle \textstyle \left\lceil (n+1)/2\right\rceil }$-sza statystyka pozycyjna^[1].

 Główny artykuł: Problem selekcji.

W algorytmice rozważa się tzw. problem wyboru, w którym dla danego zbioru ${\displaystyle n}$-elementowego oraz liczby ${\displaystyle 1\leq k\leq n}$ należy wyznaczyć ${\displaystyle k}$-tą statystykę pozycyjną w tym zbiorze. Szczególnym przypadkiem tego problemu jest problem znalezienia mediany^[1].

Nieskomplikowane rozwiązanie w złożoności ${\displaystyle O(n\log n)}$ otrzymuje się poprzez posortowanie ciągu (np. przez kopcowanie lub przez scalanie) a następnie odczytanie elementu znajdującego się w wynikowym ciągu na ${\displaystyle k}$-tej pozycji. Istnieją jednak algorytmy rozwiązujące ten problem zarówno w oczekiwanej złożoności ${\displaystyle O(n),}$ jak i algorytmy pracujące w takiej złożoności także w pesymistycznym przypadku^[1].

• mediana
• sortowanie
• algorytm Hoare’a