Mavzu: Ma’lumotlarni qidirish usullari, algoritmlari va ularning samaradorligi

MAVZU: Ma’lumotlarni qidirish usullari, algoritmlari va ularning samaradorligi

• REJA:
• Qidiruv tushunchasi va uning vazifasi
• Qidiruv usullari va algoritmlari
• Chiziqli qidiruv
• Binar qidiruv
• O’tqazishlar orqali qidiruv
• Qidiruv algoritmlari samaradorligi va mukamallashtirish usullari

Qidiruv tushunchasi va uning vazifasi

• Kompyuter va kompleks tizimlarida ma’lumotlarni qayta ishlashda qidiruv asosiy va keng foydalanadigan amallardan biri hisoblanadi.
• QIDIRUV bu ma’lumotlarning orasidan ma’lum bir belgilarga mos ma’lumotlarni topish yoki yo’qligini aniqlash jarayonidir.
• Qidiruvning maqsadi - quyidagi jarayonlarning birini bajarilishidan iborat:
• topilgan yozuvni oʼqish;
• qidirilayotgan yozuv topilmasa, uni jadvalga qoʼshish;
• topilgan yozuvni oʼchirish.

Qidiruv tushunchasi va uning vazifasi

• Qidiruvni amalga oshirayotganda 3ta xususiyat(atribut)ni ajratish mumkin:
• 1) Ma’lumotlar majmuasi - bu fayl yoki jadval ko’rinishidagi berilgan ma’lumotlar jamlanmasi (to’plami).
• 2) Kalit - ixtiyoriy maʼlumot (yoki tuzilma elementi) boshqa maʼlumotdan farqlashning biror bir belgisi.
• 3) Qidiruv mezoni – bu qidirilayotgan kalit belgisi ma’lumotlar yozuvlarida moslik sharti. (teng, yaqin, o’xshash va b.)

Kalit ikki xil boʼlishi mumkin:

• Kalit ikki xil boʼlishi mumkin:
• * Birlamchi (takrorlanmaydi, noyob);
• * Ikkilamchi (takrorlanadi).
• Kalitlar saqlanishiga nisbatan ichki va tashqi deyiladi. Agar kalitlar maʼlumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Аks holda, yaʼni yozuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi.

Qidiruv usullari va algoritmlari

• Jadvaldagi maʼlumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud:
• Chiziqli yoki ketma-ket qidiruv (Linear search)
• Binar yoki oraliqni teng ikkiga bo’lish orqali qidiruv (Binary search)
• O’tish yoki o’tqazishlar orqali qidiruv (Jump search)
• Xeshlash yoki kalitlarni akslantirish orqali qidiruv (Hash-based Search)