Mavzu: Ma’lumotlar turlari va algoritmlari, ma’lumotlarni qidirish usullari, algoritmlar va ularning samaradorligi

int search(int arr[], int N, int key)
{
int L=0, R=N-1, mid=(L+R)/2;
while (L<=R)
{
if (arr[mid] == key) return mid;
if (arr[mid] < key) L=mid+1;
else R = mid-1;
mid=(L+R)/2;
}
return -1;
}
// dasturda funktsiyadan
// foydalanish misoli
int main ()
{
int A[5] = {10,20,30,40,50};
cout << search (A,5,25);
return 0;
}

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

Izoh: algoritmdan faqatgina maʼlumotlar jadvali tartiblangan boʼlsagina foydalanish mumkin.

ALGORITM G’OYASI:

Belgilangan bosqichlarda sakrash, ya'ni elementlarning ba'zi bloklarini o'tkazib yuborish orqali (chiziqli qidiruvdan ko'ra) kamroq elementlarni tekshirishdir. Bloklarni o’tqazish uchun qadami ildiz osti N-ga teng. N – ma’lumotlarning umumiy soni.

Key = 78

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.