Interpolatsion qidiruv

ALGORITM VA MA'LUMOTLAR STRUKTURASI FANIDAN INTERPOLATSION QIDIRUV MAVZUSIDA TAYYORLAGAN KURS ISHI Mundarija I Kirish 3 II Asosiy qisim 4 2.1 Interpolatsion qidiruv tushunchasi 4 2.2 C++ da dastur ko'rinishi 14 2.3 Ikkilik qidiruvda joylashishni aniqlash 18 II Xulosa 27 IV Foydalanilgan adabiyotlar 28 Kirish Interpolatsion qidiruvning mazmuni shundan iboratki bizga malum bir tartiblangan ma'lumotlar berilgan bo'lsin. Misol uchun (massiv yoki kitob). Endi men shu ma'lumotlar 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 ma'lumotlar strukturasida qo'llanishini ko'rib chiqamiz. Interpolatsion qidiruv tushunchasi 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 ...