|
Reja: Ajrat va hukmronlik qil usuli
|
| bet | 7/7 | | Sana | 15.05.2024 | | Hajmi | 24,83 Kb. | | #234778 |
Bog'liq Algaritm mustaqil ishAlgoritm 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.
Xulosa
Xulosa qilib aytganda , bugungi kunda kesh-xotira «piramidali» o‘rnatiladi. Tezligi bo‘yicha eng tezkor, lekin hajmi bo‘yicha eng kichik birinchi darajali kesh-xotira protsessor kristalli tarkibiga kiradi. Ularni protsessor registrlari tayyorlanadigan texnologiya bo‘yicha tayyorlashadi, natijada u juda qimmat, lekin juda tezkor va eng asosiysi ishonchli bo‘lib qoldi. Uning o‘lchami atigi bir necha o‘n Kbayt bilan o‘lchanadi, lekin u tez ishlov berishda juda katta ahamiyatga ega. Ikkinchi daraja kesh-xotirasi protsessorning o‘sha kristallining o‘zida joylashishi mumkin .
Foydalanilgan adabiyotlar
1. Кленберг Дж.,Тардос Е.”Алгоритмы.Разработка и применение”.2016г.
2. Кормен Т.,Лейзерсон Ч.,Ривест Р.«Алгоритмы.Построение и анализ»,2013г.
3. Колдаев. Основы_алгоритмизации_и программирования. 2013 г.
4. Г.Уоррен «Алгоритмические трюки для программистов», 2014 г.
http://fayllar.org
|
| |
