|
Qidirish algoritmlarining qiyosiy harakteristikalari
|
| bet | 5/5 | | Sana | 08.12.2023 | | Hajmi | 99 Kb. | | #113609 |
Bog'liq MTA 144. Qidirish algoritmlarining qiyosiy harakteristikalari
Saralanmagan fayllar va massivlar uchun bir tur qidirish usullari ishlatilsa, saralangan fayl va massivlar uchun boshqa turdagi qidirish algoritmlari ishlatiladi. Quyida ularning ayrimlari bilan tanishamiz:
№
|
Algoritm nomi
|
Qiyinlik bahosi
|
Afzalligi
|
Kamchiligi
|
1.
|
Ketma-ket qidirish
|
O((n-m+1)m)
|
Saralanmagan massivlarda ishlatiladi, oddiy, kichik roʻyxatlarda juda tez
|
Katta roʻyxatlarda sekin ishlaydi
|
2.
|
Ikkilik qidirish
|
O(log n)
|
Katta roʻyxat-larda tez ish-laydi, satrli ma’lumotlar bilan yengil ishlaydi
|
|
3.
|
Interpolotsion qidirish
|
O(log n)
|
Katta roʻyxatlarda tez ishlaydi
|
Murakkab satrli ma’lumotlar bilan qiyin ishlaydi
|
Misol: Ketma-ket qidiruv va Binar qidiruv algoritmlarini solishtirishga misol.(C++ tilida)
Dastur kodi:
#include
using namespace std;
int a[101];
int main(){
int n , l=0 , r=100 , m , count1=0, count2=0;
for(int i=1; i
a[i-1]=i;
}
cout<<"Qidirilayotgan sonni kiriting: ";
cin>>n;
for(int i=0; i
if(a[i]==n) break;
count1++;
}
while(l!=r){
m=(l+r)/2;
if(m==n) break;
else if(m
else r=m-1;
count2++;
}
cout<<"Ketma-ket qidiruv algoritmi yordamida n soni "<
cout<<"Binar qidiruv algoritmi yordamida n soni "<
return 0;
}
Dastur natijasi:
5. Xulosa
Bu mustaqil ishda men ketma-ket qidiuv va ikkilik qidiruv usullarini kurib chiqdim. Bundan shunday xulosaga keldimki binar qidiruv algoritmi ketma-ket qidiruv algoritmidan ancha tez ishlar ekan. Bu degani binar qidiruv algoritmi juda yaxshi degani emas, har ikkalasiniyam vaziyatga qarab ishlatsa bo’ladi. Binar qidiruv algoritmi juda katta ro’yxatlarda tez ishlaydi, shuning uchun bu vaziyatda binar qidiruv algoritmidan foydalanish maqsadga muvofiq.
6. Foydalanilgan adabiyotlar va internet saytlari nomlari
1. Boltayev B.J , Azamatov A.R , Rahimov A.D “Algoritmlash va dasturlash asoslari” kitobi
2. A.M. Po’latov “Algoritmlash va C++ dasturlash asoslari” kitobi
3. A.R. Azamatov “Algoritmlash asoslari” kitobi
4. hozir.org
5. uzvikipediya.org
6. arxiv.uz
http://fayllar.org
|
| |
