O’tish yoki o’tqazishlar orqali qidiruv (Jump search)
// O’tish qidiruv funktsiyasi
int search(int arr[], int n, int key)
{
int i = 0, m = sqrt(n);
while (a[m] <= key && m < n)
{
i = m; m += sqrt(n);
if (m > n - 1) return -1;
}
for (int x = i; xif (a[x] == key) return x;
return -1;
}
// dasturda funktsiyadan
// foydalanish misoli
int main ()
{
int A[5] = {10,20,30,40,50};
cout << search (A,5,25);
return 0;
}
Qidiruv algoritmlari samaradorligi va mukamallashtirish usullari
Qidiruv algoritmlarining samaradorlik mezonlari
- kalitlarni taqqoslashlar soni;
- dasturning ishlab chiqishga ketgan vaqt;
- dasturni ishlashi uchun ketgan vaqt;
- talab qilinadigan xotira xajmi.
Qidiruv algoritmlari ishlab chiqilayotganida, koʼproq, jadvaldagi kalitlarni taqqoslashlar soniga (C) eʼtibor qaratiladi.
Algoritmlar samaradorligi Сmin = 1, Cmax = N, Сo’rtacha = (N+1)/2. Algoritm tartibi – chiziqli hisoblanadi - O(N) belgilanadi. С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
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.
Do'stlaringiz bilan baham: |