Muhammad al-xorazmiy nomidagi toshkent axborot

Algoritm qadamlari


Ikkilik qidirish algoritmi to'g'ri ishlashi uchun massiv saralangan bo'lishi shart! Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko'rsatkichlardan foydalanamiz. Ular massiv indekslarini ko'rsatib turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini ko'rsatadi

1. 
   Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli massiv)
   
2. 
   O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2;
   
3. 
   O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi
   
4. 
   Agar son mos kelsa, algoritm shu joyida to'xtaydi.
   
5. 
   Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta keyingi elementga suramiz: l=mid + 1;
   
6. 
   Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta oldingi elementga suramiz: r=mid — 1;
   
7. 
   2-qadamga qaytiladi.
   

Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O(logn) hisoblanadi. Solishtirish uchun Facebook misolidagi 1 mlrd login ichidan ikkilik qidirish algoritmi 30 ta (!) qadam bilan topishi mumkin. Oddiy qidirishdan tashqari bu algoritmni yana boshqa juda ko'p joyda qo'llash mumkin.
U ko'p joy egallamasdan kesh xotirasidan samarali foydalanadi, chunki u sekinroq asosiy xotiraga kirish o'rniga kesh xotirasidagi oddiy kichik muammolarni hal qiladi.
Bu Brute Force yondashuvidan ko'ra samaraliroq.
Ushbu usullar parallelizmdan qochishi sababli, u hech qanday sozlashni talab qilmasdan parallel ishlov berishdan foydalanadigan tizimlar tomonidan boshqariladi.
Rekursiya uning algoritmlarining ko'pchiligiga kiritilgan; shuning uchun u intensiv xotira boshqaruvini talab qiladi.
Bo'sh joy aniq stack tomonidan ortiqcha ishlatilishi mumkin.
Agar rekursiya protsessor to'plamidan tashqarida qattiq o'tkazilsa, tizim hatto ishdan chiqishi mumkin.
Ajratish: Ushbu bosqichda biz rekursiyadan foydalanib, muammoni kichik qismlarga ajratamiz.
Conquer: Biz kichikroq kichik qismlarni rekursiv hal qilamiz. Agar kichik muammo kichik bo'lsa, biz uni bir zumda hal qila olamiz.
Birlashtirish: dolzarb muammoni hal qilish uchun muammolarning kichik qismlarining echimlarini birlashtiring.
Qiyin muammoni osongina hal qilish mumkin.
U butun muammoni kichik muammolarga ajratadi, shuning uchun uni ko'p ishlov berishni ta'minlaydigan parallel ravishda hal qilish mumkin
Ko'p joy egallamasdan kesh xotirasidan samarali foydalanadi
Muammoning vaqt murakkabligini kamaytiradi
Murakkab masalalarni yechish: “Bo‘l va zabt et” texnikasi murakkab muammolarni kontseptual jihatdan hal qilish vositasidir. masalan. Xanoy minorasi jumboq. Bu muammoni kichik muammolarga bo'lish va ularning barchasini alohida holatlar sifatida hal qilish va keyin kichik muammolarni asl muammoga birlashtirish usulini talab qiladi.
Algoritm samaradorligi: Bo'l va zabt et paradigmasi ko'pincha samarali algoritmlarni topishda yordam beradi. Bu, masalan, Quicksort va Mergesort algoritmlari va tez Furye transformatsiyasi uchun kalit edi. Ushbu misollarning barchasida D va C yondashuvi eritmaning asimptotik narxini yaxshilashga olib keldi. Xususan, agar asosiy holatlar doimiy chegaralangan kattalikka ega bo'lsa, masalani bo'lish va qisman echimlarni birlashtirish ishi muammoning n o'lchamiga proportsional bo'ladi va har bir bosqichda o'lchamli-n/p kichik muammolarning cheklangan soni p mavjud. , u holda bo'lish va bo'lish algoritmining narxi O(n log n) bo'ladi.
Parallellik: Odatda DAC algoritmlari umumiy xotira tizimlariga ega bo'lgan ko'p protsessorli mashinalarda qo'llaniladi, bu erda protsessorlar o'rtasida ma'lumotlar almashinuvini oldindan rejalashtirish kerak emas, chunki turli xil kichik muammolar turli protsessorlarda bajarilishi mumkin.
Xotiraga kirish: Bu algoritmlar tabiiy ravishda xotira keshlaridan samarali foydalanadi. Kichik muammolar keshda sekinroq asosiy xotiradan foydalanmasdan hal qilish uchun etarlicha kichik bo'lgani uchun. Keshni samarali ishlatadigan har qanday algoritm kesh unutilgan deb ataladi.
Roundoff nazorati: yaxlitlangan arifmetika bilan hisoblashda, masalan. suzuvchi nuqtali raqamlar bilan bo'lish va bo'lish algoritmi yuzaki ekvivalent iterativ usuldan ko'ra aniqroq natijalar berishi mumkin. Masalan, har bir ma'lumotni bitta o'zgaruvchiga qo'shadigan oddiy tsikl orqali yoki ma'lumotlar to'plamini ikkiga bo'ladigan, har bir yarmining yig'indisini rekursiv hisoblaydigan D va C algoritmi orqali N sonni qo'shish mumkin va keyin qo'shiladi. ikki so'm. Ikkinchi usul birinchisi kabi bir xil miqdordagi qo'shimchalarni amalga oshirsa va rekursiv qo'ng'iroqlar uchun qo'shimcha xarajatlarni to'laydi, odatda u aniqroq bo'ladi.
Qiyin muammoni osongina hal qilish mumkin.
U butun muammoni kichik muammolarga ajratadi, shuning uchun uni ko'p ishlov berishni ta'minlaydigan parallel ravishda hal qilish mumkin
Ko'p joy egallamasdan kesh xotirasidan samarali foydalanadi
Muammoning vaqt murakkabligini kamaytiradi
Murakkab masalalarni yechish: “Bo‘l va zabt et” texnikasi murakkab muammolarni kontseptual jihatdan hal qilish vositasidir. masalan. Xanoy minorasi jumboq. Bu muammoni kichik muammolarga bo'lish va ularning barchasini alohida holatlar sifatida hal qilish va keyin kichik muammolarni asl muammoga birlashtirish usulini talab qiladi.