Sharof rashidov nomidagi samarqand davlat universiteti amaliy matematika yo

3.Ko’p tarmoqli algoritm hozirgi zamon ko’rinishidagi o’rni

Genetik algoritmlarda taqlid qilingan tabiiy tanlanish uchun qarang Tanlash (genetik algoritm).

Yilda Kompyuter fanlari, a tanlash algoritmi bu algoritm topish uchun ka-dagi eng kichik raqam ro'yxat yoki qator; bunday songa kth buyurtma statistikasi. Bunga topilgan holatlar kiradi eng kam, maksimal va o'rtacha elementlar. O bor (n) vaqt (eng yomon chiziqli vaqt) tanlash algoritmlari va tuzilgan ma'lumotlar uchun sublinear ishlash mumkin; nihoyatda, tartiblangan ma'lumotlar qatori uchun O (1). Tanlash - bu kabi murakkab muammolarning pastki muammosi eng yaqin qo'shni va eng qisqa yo'l muammolar. Ko'p tanlov algoritmlari a ni umumlashtirish orqali olinadi saralash algoritmi va aksincha ba'zi saralash algoritmlari tanlovni takroriy qo'llanilishi sifatida olinishi mumkin.
Tanlash algoritmining eng oddiy holati - bu ro'yxatni takrorlash orqali minimal (yoki maksimal) elementni topish, ishlaydigan minimal - hozirgacha minimal - (yoki maksimal) ko'rsatkichlarini kuzatib borish va quyidagilar bilan bog'liq deb ko'rish mumkin. tanlov saralash. Aksincha, tanlov algoritmining eng qiyin holati bu mediani topishdir. Aslida ixtisoslashgan median-tanlov algoritmi, bo'lgani kabi, umumiy tanlov algoritmini yaratish uchun ishlatilishi mumkin medianlar medianasi. Eng taniqli tanlov algoritmi tez tanlash bilan bog'liq bo'lgan tezkor; quicksort singari, u o'rtacha (asimptotik) eng yaxshi o'rtacha ishlashga ega, ammo eng yomon ko'rsatkichlarga ega, ammo uni eng yomon ko'rsatkichlarni ham berish uchun o'zgartirish mumkin.
Saralash bo'yicha tanlov
Ro'yxatni yoki qatorni saralash orqali kerakli elementni tanlab, tanlash mumkin kamaytirilgan ga tartiblash. 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) bo'lsa ham, tanlov O (n) yo'qligi sababli, saralangan bo'lsa ham, bog'langan ro'yxatda tasodifiy kirish. Umuman olganda saralash uchun O (n jurnal n) vaqt, qaerda n kabi taqqoslanmagan tartiblash algoritmlari bilan pastki chegara mumkin bo'lsa-da, ro'yxatning uzunligi radiks sort va hisoblash turi.
To'liq ro'yxatni yoki qatorni saralash o'rniga, undan foydalanish mumkin qisman saralash ni tanlash uchun k eng kichik yoki k eng katta elementlar. The keng kichigi (resp., kkeyin eng katta element) qisman tartiblangan ro'yxatning eng kattasi (kichik, kichik element) - bu massivga kirish uchun O (1) va O (k) ro'yxatda kirish uchun.
Tartibsiz qisman saralash
Agar qisman saralash yumshatilsa, shunday qilib k eng kichik elementlar qaytariladi, lekin tartibda emas, O (k jurnal k) ni yo'q qilish mumkin. Qo'shimcha maksimal tanlov (O olib (k) vaqt) talab qilinadi, ammo beri  , bu hali ham O ning asimptotik murakkabligini beradi (n). Aslida, bo'limlarga asoslangan tanlash algoritmlari ikkalasini ham beradi keng kichik elementning o'zi va k eng kichik elementlar (boshqa elementlar tartibda emas). Buni O (n) vaqt - ning o'rtacha murakkabligi tez tanlash va qismlarga asoslangan tanlash algoritmlarining eng yomon murakkabligi.
Aksincha, tanlash algoritmini hisobga olgan holda, tartibsiz qisman saralashni osongina olish mumkin (k eng kichik elementlar, tartibda emas) O (n) vaqtni ro'yxat bo'ylab takrorlash va barcha elementlarni kamroq qayd etish kth element. Agar bu natijadan kamroq bo'lsa k - 1 ta element, qolgan har qanday elementlar tenglikka teng kth element. Elementlarning tengligi ehtimoli tufayli ehtiyot bo'lish kerak: tarkibiga barcha elementlarni kiritmaslik kerak yoki teng The kth element, dan katta elementlar sifatida kth element ham unga teng bo'lishi mumkin.
Shunday qilib tartibsiz qisman saralash (eng past k elementlari, lekin buyurtma qilinmagan) va ni tanlash kelement juda o'xshash muammolar. Ular nafaqat bir xil asimptotik murakkablikka ega, O (n), ammo ikkalasining ham echimi to'g'ridan-to'g'ri algoritm (ikkinchisini topish k elementlari yoki ro'yxatining filtrlash elementlari kelement).
Qisman tanlov saralash
Qisman saralash orqali tanlashning oddiy misoli bu qisman foydalanishdir tanlov saralash.
Minimal (maksimal maksimal) ni topish uchun aniq chiziqli vaqt algoritmi - ro'yxat bo'yicha takrorlanish va hozirgacha minimal (maksimal maksimal) elementni kuzatib borish - eng kichik 1 elementni tanlaydigan qisman tanlov saralashi sifatida qaralishi mumkin. Biroq, boshqa ko'plab qisman navlar ham ish uchun ushbu algoritmni kamaytiradi k = 1, masalan, qisman yig'ma tartiblash.
Umuman olganda, qisman tanlov tartibida O (kn) vaqt. Bu asimptotik jihatdan samarasiz, ammo agar etarli darajada samarali bo'lishi mumkin k kichik va uni amalga oshirish oson. Aniq qilib aytganda, biz minimal qiymatni topamiz va uni boshiga o'tkazamiz, qolgan ro'yxatda to'plangunga qadar takrorlaymiz k elementlarini tanlang va keyin kth element. Qisman tanlov tartibiga asoslangan algoritm:
funktsiya tanlang (ro'yxat [1..n], k) uchun men dan 1 ga k minIndex = i minValue = ro'yxat [i] uchun j dan i + 1 ga n qil agar ro'yxat [j] keyin minIndex = j minValue = ro'yxat [j] almashtirish ro'yxati [i] va ro'yxat [minIndex] qaytish ro'yxat [k]
Bo'limga asoslangan tanlov
Qo'shimcha ma'lumotlar: Tez tanlash
Lineer ishlashga, asosan, bo'limga asoslangan tanlov algoritmi orqali erishish mumkin tez tanlash. Quickselect ning variantidir tezkor - ikkalasida ham pivotni tanlaydi, so'ngra ma'lumotlarni qismlarga ajratadi, lekin Quicksort bo'limning ikkala tomonida qasd qilsa, Quickselect faqat bir tomonida, ya'ni kerakli tomonni o'qiydi. kuchinchi element. Quicksortda bo'lgani kabi, bu o'rtacha o'rtacha ko'rsatkichga ega, bu holda chiziqli, ammo yomon ish, bu holda kvadratik. Masalan, agar ma'lumotlar allaqachon tartiblangan bo'lsa, birinchi elementni pivot sifatida qabul qilish va maksimal elementni qidirish orqali sodir bo'ladi. Amalda bunga pivo sifatida tasodifiy elementni tanlash orqali yo'l qo'ymaslik mumkin deyarli aniq chiziqli ishlash. Shu bilan bir qatorda, masalan, yanada ehtiyotkorlik bilan aniqlanadigan asosiy strategiyadan foydalanish mumkin medianlar medianasi. Ular gibridda birlashtirilgan ichki tanlov algoritm (o'xshash introsort ), Quickselect-dan boshlanadi, ammo sekinroq bo'lsa, medianlarning medianiga tushadi, natijada O o'rtacha tezligi va optimal yomon ko'rsatkichlari (n).
Bo'limga asoslangan algoritmlar odatda o'z joylarida amalga oshiriladi, bu esa ma'lumotlarni qisman saralashga olib keladi. Ular O qiymatiga ko'ra asl ma'lumotni o'zgartirmasdan joyidan tashqarida amalga oshirilishi mumkin (n) qo'shimcha joy.
Asosiy strategiya sifatida o'rtacha tanlov
Qo'shimcha ma'lumotlar: Medianlarning mediani
O'rtacha tanlov algoritmidan Quickselect yoki Quicksort-da asosiy strategiya sifatida foydalanish orqali umumiy tanlov algoritmi yoki saralash algoritmi olinishi mumkin; o'rtacha tanlash algoritmi asimptotik jihatdan optimal bo'lsa (chiziqli vaqt), natijada tanlash yoki saralash algoritmi ham bo'ladi. Aslida, aniq median shart emas - taxminiy o'rtacha etarli. In medianlar medianasi tanlash algoritmi, burilish strategiyasi taxminiy medianani hisoblab chiqadi va uni burilish sifatida ishlatadi, bu pivotni hisoblash uchun kichikroq to'plamda takrorlanadi. Amalda burama hisoblashning ustuvorligi katta ahamiyatga ega, shuning uchun odatda bu algoritmlardan foydalanilmaydi, ammo ushbu uslub algoritmlarni tanlash va saralash bilan bog'liq nazariy jihatdan qiziqish uyg'otadi.
Tafsilotlarga ko'ra, o'rtacha tanlash algoritmi berilgan, uni Quickselect-da burilish strategiyasi sifatida tanlash algoritmi olinishi mumkin. Agar o'rtacha tanlash algoritmi maqbul bo'lsa, O (n), keyin hosil bo'lgan umumiy tanlov algoritmi ham optimal bo'lib, yana chiziqli bo'ladi. Buning sababi, Quickselect a algoritmni ajratish va yutish va har bir burilishda medianadan foydalanish har qadamda qidiruv to'plamining hajmi yarimga kamayishini anglatadi, shuning uchun umumiy murakkablik geometrik qatorlar aslida har bir qadamning murakkabligi va shunchaki bitta qadamning murakkabligi doimiy ravishda ko'paytiriladi  marta (seriyani yig'ish).
Shunga o'xshab, mediani tanlash uchun qo'llaniladigan o'rtacha tanlash algoritmi yoki umumiy tanlash algoritmi berilganida, uni Quicksort-da burilish strategiyasi sifatida saralash algoritmi olinishi mumkin. Agar tanlov algoritmi maqbul bo'lsa, demak O (n), keyin olingan saralash algoritmi maqbuldir, ya'ni O (n jurnal n). Mediana saralash uchun eng yaxshi yo'nalishdir, chunki u ma'lumotlarni teng ravishda ajratadi va shu bilan tanlash algoritmini maqbul deb hisoblasa, optimal saralashni kafolatlaydi. Quicksort-da burilish strategiyasidan foydalangan holda (medianing taxminiy ko'rsatkichi) medianlar medianiga o'xshash saralash analogi mavjud va shu bilan optimal Quicksortni beradi.
Tanlov bo'yicha qo'shimcha ravishda saralash
Saralash orqali tanlovga teskari o'girilib, takroriy tanlov orqali bosqichma-bosqich saralash mumkin. Xulosa qilib aytganda, tanlov faqat bitta elementni beradi kth element. Biroq, amaliy tanlash algoritmlari tez-tez qisman saralashni o'z ichiga oladi yoki buning uchun o'zgartirilishi mumkin. Qisman saralash orqali tanlash tabiiy ravishda amalga oshiriladi, elementlarni qadar saralash k, va qismlarga ajratish bilan tanlash ba'zi elementlarni ham saralaydi: burilishlar to'g'ri holatiga, bilan kth elementi yakuniy burilishdir va burilishlar orasidagi elementlar burilish qiymatlari orasidagi qiymatlarga ega. Qisqa tanlovga nisbatan taqsimotga va taqsimotga taqqoslaganda bo'linishga asoslangan tanlovning farqi shundan iboratki, tanlovda har bir burilishning faqat bitta tomonida, faqat burilishlarni saralashda (o'rtacha log (nPivotning ikkala tomonida takrorlanadigan emas, balki burilishlar ishlatiladi).
Bu xuddi shu ma'lumotlar bo'yicha keyingi tanlovlarni tezlashtirish uchun ishlatilishi mumkin; nihoyatda to'liq tartiblangan massiv O (1) ni tanlashga imkon beradi. Bundan tashqari, avvalo to'liq saralashni bajarish bilan taqqoslaganda, takroriy tanlov orqali bosqichma-bosqich saralash amortizatsiya qiladi bir nechta tanlov bo'yicha saralash narxi.
Qisman tartiblangan ma'lumotlar uchun (gacha k), qisman tartiblangan ma'lumotlar va indeks ekan k ma'lumotlar saralanadigan ro'yxatga olinadi, keyingi tanlovlar j dan kam yoki teng k ni shunchaki tanlashi mumkin jth elementi, u allaqachon saralangan, seleksiyalar esa j dan katta k faqat yuqoridagi elementlarni saralash kerak kth pozitsiyasi.
Bo'lingan ma'lumotlar uchun, agar pivotlar ro'yxati saqlangan bo'lsa (masalan, indekslarning tartiblangan ro'yxatida), keyingi tanlovlar faqat ikkita pivot orasidagi masofani tanlashi kerak (pastki va yuqoridagi eng yaqin burilishlar). Eng katta yutuq yuqori darajadagi burilishlardan iborat bo'lib, ular qimmat bo'laklarni yo'q qiladi: ma'lumotlarning o'rtasiga yaqin bitta burilish kelajakdagi tanlovlar vaqtini yarmiga qisqartiradi. Asosiy ro'yxat keyingi tanlovlar davomida o'sib boradi, chunki ma'lumotlar yanada tartiblangan bo'ladi va hatto to'liq saralashning asosi sifatida bo'limga asoslangan sortga o'tkazilishi mumkin.


XULOSA
Saralash algoritmining bir xil qarama-qarshi turi aralashish algoritmidir . Bular tubdan farq qiladi, chunki ular tasodifiy sonlar manbasini talab qiladi. Aralashtirishni tartiblash algoritmi, ya'ni tasodifiy tartiblash orqali ham amalga oshirish mumkin: ro'yxatning har bir elementiga tasodifiy sonni belgilash va keyin tasodifiy raqamlar asosida tartiblash. Biroq, bu odatda amalda amalga oshirilmaydi va aralashtirishning mashhur oddiy va samarali algoritmi mavjud. Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma‟nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma‟lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi. Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, shu tartibda qoldirilishi maqsadga muvofiq bo’ladi (Bir xil kalitlilar o’zlariga nisbatan).