• Algoritm qadamlari
  • Foydalanilgan adabiyotlar
  • Foydalanilgan veb-sahifalar
    		•

    Chiziqli qidirish algoritmi




    Download 199,62 Kb.
    bet6/6
    Sana15.05.2024
    Hajmi199,62 Kb.
    #234109
    1   2   3   4   5   6
    Bog'liq
    Qo\'ziboyev Jamshid Algoritmlarni Loyihalash

    Chiziqli qidirish algoritmi
    Chiziqli qidirish algoritmi juda oddiy algoritm bo'lib, u massivdagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm murakkabligi O(n) bo'lib, bu real hayotda juda ham sekin bo'lishi mumkin. Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o'z profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10⁶ ta loginni tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000 soniya (16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar uchun bizga samaraliroq algoritmlar kerak bo'ladi.
    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 .


    Foydalanilgan adabiyotlar
    1.Кленберг Дж.,Тардос Е.”Алгоритмы.Разработка и применение”.2016г.
    2. Кормен Т.,Лейзерсон Ч.,Ривест Р.«Алгоритмы.Построение и анализ»,2013г.
    3. Колдаев. Основы_алгоритмизации_и программирования. 2013 г.
    Foydalanilgan veb-sahifalar:

    1. Youtube.com - Fireship, freecode kanallari.

    2. https://lms.tuit.uz/student/my-courses

    3. https://en.wikibooks.org/wiki/Numerical_Methods/Equation_Solving

    4. https://www.remove.bg/upload



    TOSHKENT 2024

    Download 199,62 Kb.
    1   2   3   4   5   6




    Download 199,62 Kb.