“ A LGOR I TM VA M A’ L UM OTL A R STR UK TUR A SI ” FA N I DA N “ I N TER POL ATSI ON QI DI R UV ” M AV ZUSI DA TAY Y OR L AGA N   KURS I SHI  

Mu n da ri j a I K i r i sh .................................................................................................... ......3 I I A sosi y qi si m ..............................................................................................4 2.1 I n t er pol a t si on qi di r u v t u sh u n c h a si . .............................................4 2.2 C++ da da st u r k o` r i n i sh i ..............................................................14 2.3 I k k i l i k qi di r u v da j oy l a sh i sh n i a n i ql a sh ...... ..... .............................18 I I I X u l osa .................................................................................................. ..27 I V Foy da l a n i l ga n a da bi y ot l a r ...................................................................28

Kirish Interpolatsion qidiruvning mazmuni shundan iboratki bizga malum bir tartiblangan ma’lumotlar berilgan bo‘lsin. Misol uchun (massiv yoki kitob). Endi men shu malumotlar orasidan bitta qiymat yoki sozni izlab topishim kerak. Buni men interpolatsion qidiruv orqali amalga oshiraman. Ammo ikkilik qidiruvdan farqli o'laroq, interpolyatsiya qidiruvi ketma-ketlikni ikkita teng qismga ajratmaydi, balki elementning talab qilinadigan va joriy qiymati o'rtasidagi masofaga e'tibor qaratgan holda kalitning (kerakli element) taxminiy joylashishini hisoblab chiqadi. Lug`at kitobda so`zlar alfavit (alifbo) tarzida tartiblangan bo`ladi, yani kitobning boshidagi so`zlar “a” harfidan boshlansa, oxiridagi so`zlar “z” harfi bilan tugaydi. Bizga kerakli so`z “olma” bo`lsin. Olma so`zini kitobning boshidan izlamaymiz, chunki “o” harfi alfavitning o`rtasida joylashgani uchun, olma so`zini topish uchun kitobning o`rtasini ochamiz va o harfidan boshlangan so`zlar orasidan qidirib topamiz. Bunda olma so`zini kitobning boshidan ohirigacha izlamaymiz balki o harfi qatnashgan so`zlar orasidan oson topamiz. Bundan ko`rinib turibdiki boshq sohalarda ham interpolatsion qidiruv dan foydalanami. Interpolatsion so`zining ma’nosini tushinib oldik. Endi bu interpolatsion qidiruvni algaritim va malumotlar strukturasida qo`llanishini ko`rib chiqamiz.

I n t er pol a t si on qi di r u v t u sh u n ch a si Interpolyatsiya – bu ma'lum qiymatlarning mavjud diskret to'plamidan miqdorning oraliq qiymatlarini topishdir. Interpolatsiya qidiruvi faqat tartiblangan massivlar bilan ishlaydi.  U binarga o'xshaydi, ya'ni har bir qadamda ma'lum bir qidiruv maydoni hisoblab chiqiladi, algoritm bajarilganda u torayadi.Ammo ikkilik qidiruvdan farqli o'laroq, interpolyatsiya qidiruvi ketma-ketlikni ikkita teng qismga ajratmaydi, balki elementning talab qilinadigan va joriy qiymati o'rtasidagi masofaga e'tibor qaratgan holda kalitning (kerakli elementini) taxminiy joylashishini hisoblab chiqadi.Algoritm g'oyasi telefon raqamini qidirishni eslatadi: abonent nomlari ro'yxati tartiblangan, shuning uchun kerakli telefon raqamini topish qiyin bo'lmaydi, chunki, masalan, biz "U" harfi bilan boshlanadigan familiyasi bo'lgan obunachini qidirayotgan bo'lsak, unda qidirish uchun ma'lumotnomaning oxiriga o'tish maqsadga muvofiq bo'ladi. Hisoblangan qiymat kattaroq bo'lsa, qidiruv maydonining o'ng chegarasi, agar u kamroq bo'lsa, chap tomonga siljiydi.

Foydalanish paytida katta ma'lumotlar n uchun interpolatsion qidiruv algoritm ishlash O (n); ammo interpolatsiya uchun ishlatiladigan chiziqli shkala bo'yicha ma'lumotlar teng taqsimlangan deb faraz qilsak, unumdorlik O (log log n) sifatida ko'rsatilishi mumkin. Interpolyatsiyani qidirishning amaliy samaradorligiga qarab sonining kamayishi har bir takrorlash uchun zarur bo'lgan murakkabroq hisob- kitoblardan ustun bo'ladimi-yo'qligiga bog'liq. Bu diskdagi katta tartiblangan fayldagi yozuvni topish uchun foydali bo'lishi mumkin. B- daraxtlar kabi indeks tuzilmalari diskka kirishni ham kamaytiradi va ko'pincha diskdagi ma'lumotlarni qisman indekslash uchun ishlatiladi, chunki ular ko'p turdagi ma'lumotlarni indekslashi va onlayn ravishda yangilanishi mumkin . Biroq, diskda ma'lum tartiblangan, lekin indekslanmagan ma'lumotlar to'plamini qidirishga majbur bo'lganda, interpolyatsiya qidiruvi foydali bo'lishi mumkin.