4-mustaqil ishi qarshi-2022

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

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.