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 $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^[1].

Wyznaczanie

Główny artykuł: Problem selekcji.

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^[1].

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^[1].

Zobacz też

Przypisy

↑ ^a ^b ^c ^d ThomasT. Cormen ThomasT. i inni, Wprowadzenie do algorytmów, Warszawa: Wydawnictwo Naukowe PWN, 2012, s. 210-211, ISBN 978-83-01-16911-4 (pol.).

[:0-1] ThomasT. Cormen ThomasT. i inni, Wprowadzenie do algorytmów, Warszawa: Wydawnictwo Naukowe PWN, 2012, s. 210-211, ISBN 978-83-01-16911-4 (pol.).

[1]