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

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.

• 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).