4-mavzu: Ma’lumotlarni qidirish usullari, algoritmlari va ularning samaradorligi

O’tish yoki o’tqazishlar orqali qidiruv (Jump search)

Qidiruv algoritmlari samaradorligi va mukamallashtirish usullari

Algoritmlar samaradorligi

• Chiziqli qidiruv algoritmi
• Сmin = 1, Cmax = N, Сo’rtacha = (N+1)/2.
• Algoritm tartibi – chiziqli hisoblanadi - O(N) belgilanadi.
• Binar qidiruv algoritmi
• Сmin = 1, Cmax = log2(N)
• Algoritm tartibi – logarifmik hisoblanadi – O(logN) belgilanadi.
• O’tish qidiruv algoritmi
• p – qadam o’lchovi
• Сmin = 1+1, Cmax = √n + √n
• Algoritm tartibi - O(√n) belgilanadi.

• Chiziqli qiduruvni Mukamallashtirish usullari

• Topilgan elementni jadval boshiga qoʼyish orqali jadvalni qayta tartiblash;
• Transpozitsiya usuli.

• Birinchi usulni magʼzi shundan iboratki, berilgan kalitga teng kalitli element jadvalda birinchi element deb oʼzlashtiriladi, qolganlari esa suriladi.
• Keltirilgan algoritm roʼyxat uchun ham massiv uchun xam oʼrinli. Biroq bu algoritm massiv uchun tavsiya qilinmaydi, sababi elementlarni oʼrinlashtirishga koʼrsatkichlarni oʼrinlashtirishdan koʼra ancha koʼp vaqt talab qiladi.

• Transpozitsiya usulida topilgan element jadvalda bitta oldingi element bilan oʼrin almashtiriladi. Аgarda mazkur elementga koʼp murojaat qilinsa, bittadan oldinga surilib borib natijada jadval boshida boʼladi.
• Ushbu usul nafaqat roʼyxatda, balki massivda xam qulay (sababi faqatgina ikkita yonma-yon turgan element oʼrin almashtiriladi).