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].

Wyznaczanie

 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].

Zobacz też

• mediana
• sortowanie
• algorytm Hoare’a

Przypisy

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.).

Kontrola autorytatywna (statystyka):

• LCCN: sh85095364
• GND: 4212486-4
• BnF: 119782494
• BNCF: 45876
• NKC: ph136932
• J9U: 987007550947005171