Reja qidiruv tushunchasi va uning vazifasi Chiziqli qidiruv (kerma –ket ) Indeksli ketma ket qidiruv

Qidiruv algoritmlarining samaradorligi

• Ma’lumki, qidiruvning maqsadi - quyidagi jarayonlarni bajarilishidan iborat:
• topilgan yozuvni o‘qish.
• qidirilayotgan yozuv topilmasa, uni jadvalga qo‘yish.
• topilgan yozuvni o‘chirish.
• Qidiruv algoritmlarining samaradorlik mezonlari:
• kalitlarni taqqoslashlar soni;
• dasturning ishlab chiqishga ketgan vaqt;
• talab qilinadigan xotira xajmi.
• Qidiruv algoritmlari ishlab chiqilayotganida, asosan, ko‘proq, jadvaldagi kalitlarni taqqoslashlar soniga e’tibor qaratiladi.
• Faraz qilaylik, ketma-ket qidiruv algoritmida taqqoslashlar soni -M, indeksli ketma-ket qidiruvda esa - S bo‘lsin. U holda:
• Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo‘ladi, O(n):
• M =1 n, Mo‘rtacha = (n + 1)/2.

Eslatma: Ma’lumotlar jadvali massiv yoki bog‘lamli ro‘yxat ko‘rinishida bo‘ladi.

• Eslatma: Ma’lumotlar jadvali massiv yoki bog‘lamli ro‘yxat ko‘rinishida bo‘ladi.
• Eslatma: Massiv va bog‘langan ro‘yxatda kerakli elementni bor yoki yo‘qligini aniqlash samaradorligi bir xil, ammo topilgan elementni o‘chirish yoki bunday element jadvalda bo‘lmasa, uni jadvalga qo‘yish talab qilingan bo‘lsa, u holda qidiruvni amalga oshirish ro‘yxatda samaraliroq bo‘ladi.
• Indeksli ketma-ket qidiruv samaradorligi
• Faraz qilaylik, kalitlar teng extimolli bilan tekis taqsimlangan, u holda samaradorlikni quyidagicha hisoblash mumkin:
• S = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1, bu erda: m – indeks o‘lchovi; m = n / p; p – qadam o‘lchovi.
• dS/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p2 + 1/2 = 0 p2=n popt=
• Demak, indeksli ketma-ket qidiruvni samaradorligi tartibi bo‘ladi.

• →

• →

2-Mavzu bo‘yicha nazorat savollari

• 1. Qidiruv deganda nima tushiniladi?
• 2. Qidiruvning vazifasi nimadan iborat?
• 3. Qidiruvning maqsadi nimadan iborat?
• 4. Chiziqli qidiruvning g‘oyasini tushuntirib bering?
• 5. Indeksli ketma-ket qidiruv tushunchasi?
• 6.Binar qidiruv nima?