|
Mirzo Ulug’bek nomidagi O’zbekiston Milliy universiteti Jizzax filiali “Amaliy matematika” fakulteti
|
| bet | 6/8 | | Sana | 14.05.2024 | | Hajmi | 37,56 Kb. | | #233609 |
Bog'liq Mirzo Ulug’bek nomidagi O’zbekiston Milliy universiteti Jizzax f-www.hozir.orgTartibli 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 kucha ni qurish va keyin undan O(n+k logn)=O(n) vaqtda k ta eng kichik elementlarni tanlash kerak. Xuddi shunday k≥n-n/logn bo‘lganda O(n) vaqt ichida k-tartibli statistikani topish mumkin.
Tez tartiblash variantlari. O‘rta holatda k-tartibli statistikani topish uchun tez tartiblash usuliga asoslangan protsedurani rekursiv ishlatiladi. Bu protsedurani select (tanlash) deb nomlaymiz. select(l, j, k) protsedurasi qandaydir katta A[1], ..., A[n] massivdan olingan A[i], ..., A[j] elementlar orasidan k – elementni topadi. select protsedurasi quyidagi harakatlarni bajaradi.
1. Tayanch elementni tanlash, masalan υ.
2. partition protsedurasini ishlatib, A[i], ..., A[j] elementlarni ikki guruhga bo‘lish. Birinchi A[i], ..., A[m-1] guruhda barcha yozuvlarning kalit υ dan kichik, ikkinchi A[m], ..., A[j] guruhda—υ ga teng yoki katta.
3. Agar k≤m-i bo‘lsa, u holda k-element birinchi guruhda joylashadi va unga yana select(i, m-1, k) protsedurasi qo‘llaniladi. Agar k>m-i bo‘lsa, u holda select(m, j, k-m+ i) protsedurasi chaqiriladi.
Bir xil qiymatlardagi kalitlarga ega bo‘lgan A[i], ..., A[j] elementlar uchun select(i, j, k) protsedurasi ertami-kech chaqiriladi (va shuning uchun i=j bo‘ladi). Bu elementlarning kalitlari izlanayotgan k-tartibli statistika qiymati bo‘ladi.
Tez tartiblash usulidagidek, select protsedurasi eng yomon holatda Ω(n2) dan kam bo‘lmagan vaqt talab qiladi. Masalan, agar eng kichik elementni topishda tayanch element sifatida har doim kalit qiymatlaridan eng kattasini olish kerak, u holda bu protsedura uchun bajarilish vaqti O(n2) tartibda bo‘ladi. Lekin o‘rta holatda select protsedurasi tez tartiblash algoritmiga nisbatan tez ishlaydi, o‘rtacha u O(n) vaqtda bajariladi. Bu algoritmlar orasidagi farq shundan iboratki, tez tartiblash protsedurasi ikki marta chaqirilganda, select protsedurasi bir marta chaqiriladi. Select protsedurasining tahlili tez tartiblash protsedurasining tahlilidek bo‘ladi. Bu protsedura avvalgi qadamda chaqirilgan to‘plamning bir qismi bo‘lib hisoblangan qism to‘plamda o‘zini takroran chaqiradi. Bu protseduraning har bir chaqirilishi protseduraning avvalgi chaqirilishi amalga oshirilgan to‘plamning 9/10 qismidan iborat bo‘lgan elementlar to‘plamida amalga oshiriladi. U holda, agar T(n) orqali n ta elementdan iborat to‘plamda select protsedurasiga ketgan vaqtni belgilasak, qandaydir o‘zgarmaslar uchun quyidagilarga ega bo‘lamiz:
T(n)≤T(9/10* n) + sn (1.14)
(1.14) T(n) = O(n) teng bo‘lishini ko‘rsatish qiyin emas.
|
| |
