|
Binar qidiruv (teng ikkiga bo’lish usuli)
|
| bet | 4/8 | | Sana | 07.10.2024 | | Hajmi | 1 Mb. | | #273965 |
Bog'liq Ma\'lumotlar tuzilmasi va algaritim-1Binar qidiruv (teng ikkiga bo’lish usuli).
Faraz qilaylik, o’sish tartibida tartiblangan sonlar massivi berilgan bo’lsin. Ushbu usulni asosiy g’oyasi shundan iboratki, tasodifiy qandaydir AM element olinadi va u X qidiruv argumenti bilan taqqoslanadi. AgarAM=X bo’lsa, u holda qidiruv yakunlanadi; agar AM M >X bo’lsa.
M ixtiyoriy tanlanganda ham taklif qilinayotgan algoritm korrekt ishlaydi. Shu sababali M ni shunday tanlash lozimki, tadqiq qilinayotgan algoritm samaraliroq natija bersin, ya’ni uni shunday tanlaylikki, iloji boricha kelgusi jarayonlarda ishtirok etuvchi elementlar soni kam bo’lsin. Agar biz o’rtacha elementni, ya’ni massiv o’rtasini tanlasak yechim mukammal bo’ladi.
Qidirish usullari samaradorligi va optimallashtirish.
Ketma-ket qidiruvni samaradorligi. Ixtiyoriy qidiruvning samaradorligi jadvaldagi ma’lumotlarning kalitlari bilan solishtirish soni – S bilan baxolanishi mumkin. Agar taqqoslashlar (solishtirish) soni qancha kichik bo’lsa, qidiruv algoritmi samaradorligi shuncha yaxshi bo’ladi.
Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo’ladi:
C = 1 n, C = (n + 1)/2.
Umuman olganda ro’yxatda xam samaradorlik yuqoridagi kabi bo’ladi. Garchi massivda xam bog’langan ro’yxatda xam qidiruv samaradorligi bir xil bo’lsada, ma’lumotlarni massiv va ro’yxat ko’rinishda tasvirlashning o’ziga xos kamchilik va afzalliklari mavjud. Qidiruvning maqsadi - quyidagi jarayonlarni bajarilishidan iborat:
Topilgan yozuvni o’qish.
Qidirilayotgan yozuv topilmasa, uni jadvalga qo’yish.
Topilgan yozuvni o’chirish.
Birinchi jarayon (qidiruvning o’zi) massiv uchun ham ro’yxat uchun ham bir xil bo’ladi. Ikkinchi va uchinchi jarayonda esa qidiruv ro’yxatli tuzilmada samaraliqroq bo’ladi (sababi massivda elementlarn siljitish lozim).
Agar k massivda elementlarni siljitishlar soni bo’lsa, u xolda k = (n + 1)/2
bo’ladi.
|
| |
