Ўзбекистон республикаси алока ва

Tartibli  statistika. 

Tartibli  statistikani  hisoblash  masalasi  quyidagidan  iborat:  n 

ta  elementdan  iborat  ro‘yxat  va  k  butun  son  berilgan,  o‘sish  tartibida  tartiblangan 

ro‘yxatda  k-pozitsiyada  turgan  yozuv  kalitini  topish  kerak.  Qisqartirib  bu  masalani 

«k-tartibli  statistikani  topish  masalasi»  deb  ataymiz.  Bu  masalaning  maxsus  hollari 

k=1  (eng  kichik  elementni  topish),    k=n  (eng  katta  elementni  topish)  va  agar  n  toq 

bo‘lsa, k=(n+1)/2

 

(medianani topish) da paydo bo‘ladi.  

Ayrim  hollarda  tartibli  statistikani  hisoblash  masalasi  chiziqli  vaqtda  topiladi. 

Masalan,  minimal  (maksimal)  elementni  topish  O(n)  tartibli  vaqtni  talab  etadi.

 

Agar 

k≤n/logn bo‘lsa, u holda k- tartibli statistikani topish uchun