Guruhi talabasining
Download 0.59 Mb. Pdf ko'rish
|
ALGORITMLARNI LOYIHALASH
|
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. 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 . Download 0.59 Mb. Do'stlaringiz bilan baham: 
|