|
6-mavzu: To’la va qisman tanlov algoritmlari
Reja.
To’la tanlov algoritmlari
Tartibsiz qisman saralash
Qisman tanlov saralash
Informatika fanida tanlov algoritmi bu ro'yxat yoki massivdagi k-sonli sonni topish algoritmi; bunday son k-darajali statistika deb ataladi. Bunga minimal, maksimal va o'rtacha elementlarni topish hollari kiradi. O (n) -time (eng yomon holatdagi chiziqli vaqt) tanlash algoritmlari mavjud va tuzilgan ma'lumotlar uchun sublinear ishlash mumkin; nihoyatda, tartiblangan ma'lumotlar qatori uchun O (1). Tanlov - bu eng yaqin qo'shni va eng qisqa yo'l muammolari kabi murakkab muammolarning subproblemasi. Ko'plab tanlash algoritmlari saralash algoritmini umumlashtirish orqali olinadi va aksincha ba'zi saralash algoritmlari tanlovni takroriy qo'llanilishi sifatida olinishi mumkin.
Tanlash algoritmining eng oddiy holati - bu minimal (yoki maksimal) elementni ro'yxat bo'ylab takrorlash orqali topish, ishlaydigan minimal - hozirgacha minimal - (yoki maksimal) ko'rsatkichlarini kuzatib borish va tanlov saralash bilan bog'liq deb ko'rish mumkin. Aksincha, tanlov algoritmining eng qiyin holati bu mediani topishdir. Aslida, medianlar medianasida bo'lgani kabi, umumiy tanlov algoritmini tuzishda ixtisoslashgan median-tanlov algoritmidan foydalanish mumkin. Tanlovning eng taniqli algoritmi Quickselect bo'lib, u Quicksort bilan bog'liq; Quicksort singari, u o'rtacha (asimptotik) maqbul o'rtacha ko'rsatkichga ega, ammo eng yomon ko'rsatkichlar, ammo uni eng yomon ko'rsatkichlarni ham berish uchun o'zgartirish mumkin.
Ro'yxat yoki qatorni saralash orqali kerakli elementni tanlab, saralashga saralashgacha qisqartirish mumkin. Ushbu usul bitta elementni tanlash uchun samarasiz, ammo massivdan ko'plab tanlovlarni o'tkazish kerak bo'lganda samarali bo'ladi, bu holda faqat bitta boshlang'ich, qimmat saralash kerak bo'ladi, undan keyin ko'plab arzon tanlov operatsiyalari - massiv uchun O (1) , tasodifiy kirishning etishmasligi sababli, saralangan bo'lsa ham, bog'langan ro'yxatda tanlov O (n) bo'lsa ham. Umuman olganda, saralash uchun O (n log n) vaqt kerak bo'ladi, bu erda n - ro'yxatning uzunligi, ammo pastki chegara radiaks sort va count sort kabi taqqoslanmagan tartiblash algoritmlari bilan mumkin bo'lsa ham.
Butun ro'yxatni yoki qatorni saralash o'rniga, eng kichik yoki k kattaroq elementlarni tanlash uchun qisman saralashdan foydalanish mumkin. Keyinchalik kichkina k (eng katta element), qisman tartiblangan ro'yxatning eng kattasi (resp., Eng kichik element) - bu O (1) qatorga kirish uchun va O (k) - ro'yxatga kirish uchun
Tartibsiz qisman saralash
Agar qisman saralash eng kichik k elementlar qaytarilishi uchun yumshatilsa, lekin tartibda bo'lmasa, O (k log k) omilini yo'q qilish mumkin. Qo'shimcha maksimal tanlov (O (k) vaqtni olish) talab qilinadi, ammo {\ displaystyle k \ leq n} k \ leq n bo'lgani uchun, bu hali ham O (n) ning asimptotik murakkabligini keltirib chiqaradi. Darhaqiqat, bo'linishga asoslangan tanlash algoritmlari k-chi elementning o'zi va k-ning eng kichik elementlarini oladi (boshqa elementlar tartibda emas). Buni O (n) vaqt ichida amalga oshirish mumkin - Quickselectning o'rtacha murakkabligi va eng yomon holatdagi murakkab bo'linmalarga asoslangan tanlash algoritmlari.
Aksincha, tanlash algoritmini hisobga olgan holda, ro'yxatni takrorlash va k elementidan kam bo'lgan barcha elementlarni yozish orqali O (n) vaqt ichida tartibsiz qisman saralashni (k kichik elementlar, tartibda emas) osongina olish mumkin. Agar bu k - 1 dan kam elementga olib keladigan bo'lsa, qolgan elementlar k elementiga tenglashadi. Elementlarning tengligi ehtimoli tufayli ehtiyot bo'lish kerak: k elementga teng yoki teng bo'lmagan barcha elementlarni o'z ichiga olmaydi, chunki k elementdan kattaroq elementlar ham unga teng bo'lishi mumkin.
Shunday qilib tartibsiz qisman saralash (eng past k elementlar, lekin buyurtma qilinmagan) va k elementni tanlash juda o'xshash muammolar. Ular nafaqat bir xil asimptotik murakkablikka ega (O (n)), balki ikkalasining ham echimini boshqasiga to'g'ridan-to'g'ri algoritm (max k elementlarini topish yoki ro'yxatning elementlarini filtrlash) yordamida hal qilish mumkin. k-element qiymatining kesilishi).
Qisman tanlov saralash
Qisman saralash orqali tanlashning oddiy misoli bu qisman tanlash saralashidan foydalanishdir.
Minimal (maksimal maksimal) ni topish uchun aniq chiziqli vaqt algoritmi - ro'yxat bo'yicha takrorlash va shu paytgacha minimal (maksimal maksimal) elementni kuzatib borish - 1 ta eng kichik elementni tanlaydigan qisman tanlov saralashi sifatida qaralishi mumkin. Shu bilan birga, boshqa ko'plab qisman navlar, shuningdek, k = 1 holati uchun ushbu algoritmni qisqartiradi, masalan, qisman yig'ma tartiblash.
Umuman olganda qisman tanlov saralashi O (kn) vaqtni talab qiladigan oddiy tanlov algoritmini beradi. Bu asimptotik jihatdan samarasiz, ammo agar k kichik bo'lsa va uni bajarish oson bo'lsa, etarli darajada samarali bo'lishi mumkin. Aniq qilib aytganda, biz minimal qiymatni topamiz va uni boshiga o'tkazamiz, qolgan elementlarni k elementlar yig'ilguncha takrorlaymiz va keyin k elementni qaytaramiz. Qisman tanlov asosida saralash algoritmi:
function select(list[1..n], k)
for i from 1 to k
minIndex = i
minValue = list[i]
for j from i+1 to n do
if list[j] < minValue then
minIndex = j
minValue = list[j]
swap list[i] and list[minIndex]
return list[k]
Do'stlaringiz bilan baham: |
