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.

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

Wyznaczanie

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

Nieskomplikowane rozwiązanie w złożoności $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 $k$-tej pozycji. Istnieją jednak algorytmy rozwiązujące ten problem zarówno w oczekiwanej złożoności $O(n),$ jak i algorytmy pracujące w takiej złożoności także w pesymistycznym przypadku.

Zobacz też

• mediana
• sortowanie
• algorytm Hoare’a