INTERPOLATSION QIDIRUV
![usullarining universal nomi, ammo bu harakatni amalga oshirish usullarining
xilma-xilligi ularni ushbu harakatga bo'ysunadigan funktsiya turiga qarab
guruhlarga bo'linishga majbur qiladi. Ya’ni, biz yuqorida ko'rib chiqqan
interpolatsiya to'g'ridan -to'g'ri usullarni nazarda tutadi. Shuningdek, teskari emas,
balki teskari funktsiyani (ya'ni, y dan x) hisoblash imkonini beruvchi teskari
interpolatsiya ham mavjud. Biz oxirgi variantlarni ko'rib chiqmaymiz, chunki bu
juda qiyin va yaxshi matematik bilimlar bazasini talab qiladi.
Keling, eng muhim bo'limlardan biriga o'taylik. Undan biz muhokama
qilayotgan usullar to'plami hayotda qanday va qaerda qo'llanilishini bilib olamiz.
Interpolatsiya usullari
Interpolatsiya muammosi bayoni
Ko'pincha ph (X) funktsiyasini aniqlash uchun interpolyatsiya masalasining
bayonoti deb ataladigan bayonot ishlatiladi.
Interpolatsiya muammosining bu klassik formulasida taxminiy analitik
funktsiyani aniqlash kerak bo'ladi φ (X), uning qiymatlari tugun nuqtalarida
Xi. qiymatlarga mos keladi Asl jadvalning Y (X i), ya'ni. shartlar
(X i) = Y i (i = 0,1,2, ...,ϕ
n)
Shunday qilib tuzilgan taxminiy funksiya φ (X) argument qiymatlari [X 0;
Xn], jadval bilan aniqlangan. X argumentining qiymatlarini belgilashda, tegishli
emas bu intervalda interpolatsiya muammosi ekstrapolyatsiya muammosiga
aylanadi. Bunday hollarda aniqlik ph (X) funktsiyasi qiymatlarini hisoblashda
olingan qiymatlar X argumenti qiymatining X 0 dan masofasiga bog'liq, agar X
bo'lsa Х 0 , Х n , Х >X n.
Matematik modellashtirishda interpolyatsiya funktsiyasidan foydalanib,
tekshirilayotgan funksiyaning pastki oraliq oraliq nuqtalarida taxminiy
qiymatlarini hisoblash mumkin [X i; X i + 1]. Ushbu protsedura deyiladi siqish
jadvali.
9](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_9.png)
![Interpolyatsiya algoritmi ph (X) funksiyasining qiymatlarini hisoblash usuli
bilan aniqlanadi. Interpolyatsiya funksiyasining eng oddiy va eng aniq amalga
oshirilishi tekshirilayotgan Y (X) funksiyani [X i oraliqda; X i + 1] Y i, Y i + 1
nuqtalarni bog'laydigan to'g'ri chiziqli segment orqali. Bu usul chiziqli
interpolatsiya usuli deyiladi.
Chiziqli interpolyatsiya
Chiziqli interpolatsiya bilan X i va X i + 1 tugunlari orasidagi X nuqtadagi
funktsiyaning qiymati jadvalning ikkita qo'shni nuqtasini bog'laydigan to'g'ri chiziq
formulasi bilan aniqlanadi.
Y (X) = Y (Xi) + Y (Xi + 1) - Y (Xi)
(X - Xi) (i = 0,1,2, ..., n),
X i + 1− X i
Shaklda. 1da ma'lum bir miqdordagi Y (X) o'lchovlari natijasida olingan
jadval misoli ko'rsatilgan. Manba jadvalining qatorlari to'ldirish bilan ta'kidlangan.
Jadvalning o'ng tomonida bu jadvalga mos keladigan tarqoqlik chizig'i joylashgan.
Jadvalni siqish formula bo'yicha hisoblash tufayli amalga oshiriladi.
(3) pastki intervallarning o'rta nuqtalariga to'g'ri keladigan X nuqtalaridagi
taxminiy funktsiyaning qiymatlari (i = 0, 1, 2,…, n).
Kondensatsiyalangan Y (X) funktsiya jadvali va tegishli diagramma
Grafikni ko'rib chiqayotganda. 1 dan ko'rinib turibdiki, jadvalni chiziqli
interpolyatsiya usuli bilan siqish natijasida olingan nuqtalar dastlabki jadval
nuqtalarini bog'laydigan chiziq segmentlarida yotadi. Chiziqli
aniqlikinterpolatsiya, asosan, interpolatsiyalangan funktsiyaga va X i , X i + 1
jadval tugunlari orasidagi masofaga bog'liq.
Shubhasiz, agar funktsiya silliq bo'lsa, tugunlar orasidagi masofa nisbatan
katta bo'lsa ham, nuqtalarni chiziq segmentlari bilan bog'lash orqali tuzilgan grafik
Y (X) funktsiyasining tabiatini etarlicha aniq baholashga imkon beradi. Agar
funktsiya etarlicha tez o'zgarsa va tugunlar orasidagi masofa katta bo'lsa, chiziqli
10](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_10.png)
![Interpolatsiya qidiruvi ikkilik qidiruvning takomillashtirilgan
versiyasidir. Ushbu qidiruv algoritmi kerakli qiymat o'lchanadigan nuqtada
ishlaydi. Ushbu algoritm to'g'ri ishlashi uchun ma'lumotlar to'plami tartiblangan
va bir tekis taqsimlanishi kerak.
Ikkilik qidiruv chiziqli qidiruvga nisbatan katta vaqt murakkabligi
ustunligiga ega. Chiziqli qidiruvning eng yomon murakkabligi n (n), ikkilik
qidiruv esa n (log n) ga ega.
Maqsadli ma'lumotlarning joylashuvi oldindan ma'lum bo'lishi mumkin bo'lgan
holatlar mavjud. Masalan, telefon ma'lumotnomasida, agar biz Morfinning
telefon raqamini topmoqchi bo'lsak. Bu erda chiziqli qidiruv va hatto ikkilik
qidiruv sekin ko'rinadi, chunki biz to'g'ridan-to'g'ri "M" bilan boshlangan nomlar
saqlanadigan xotira maydoniga o'tishimiz mumkin.
C++ da dastur ko`rinishi
#include <iostream>
using namespace std;
int main()
{
int MyArray [] { 1, 2, 4, 6, 7, 89, 123, 231, 1000, 1235 };
int x = 0;
int a = 0;
int b = 9;
int WhatFind = 123;
bool found;
13](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_13.png)
![for (found = false; (MyArray[a] < WhatFind) && (MyArray[b] > WhatFind)
&& !found; )
{
x = a + ((WhatFind - MyArray[a]) * (b - a)) / (MyArray[b] - MyArray[a]);
if (MyArray[x] < WhatFind)
a = x + 1;
else if (MyArray[x] > WhatFind)
b = x - 1;
else
found = true;
}
if (MyArray[a] == WhatFind)
cout << WhatFind << " asos element " << a << endl;
else if (MyArray[b] == WhatFind)
cout << WhatFind << " asaos element " << b << endl;
else
cout << "kechirasiz topilmadi" << endl;
return 0;
}
Natija (1-rasm).
14](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_14.png)
![1-rasm.
C++ da dastur kodi
//#include "stdafx.h"
#include <iostream>
using namespace std;
const int N=17;
//интерполяционный поиск
int InterpolSearch(int A[], int key)
{
int mid, left=0, right=N-1;
while (A[left]<=key && A[right]>=key)
{
mid=left+((key-A[left])*(right-left))/(A[right]-A[left]);
if (A[mid]<key) left=mid+1;
else if (A[mid]>key) right=mid-1;
else return mid;
}
if (A[left]==key) return left;
15](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_15.png)
![else return -1;
}
//главная функция
int main()
{
setlocale(LC_ALL,"Rus");
int i, key;
int A[N]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
cout<<"Искомый элемент > "; cin>>key; //ввод ключа
cout<<"Исходный массив: ";
for (i=0; i<N; i++) cout<<A[i]<<" "; //вывод массива
if (InterpolSearch(A, key)==-1) cout<<"\nЭлемент не найден";
else cout<<"\nНомер элемента: "<<InterpolSearch(A, key)+1;
system("pause>>void");
}
Natija (2-rasm).
2- rasm .
16](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_16.png)
![Ikkilik qidiruvda joylashishni aniqlash
Ikkilik qidiruvda, agar kerakli ma'lumotlar topilmasa, qolgan ro'yxat ikki
qismga bo'linadi, pastki va yuqori. Ularning har birida qidiruv ishlari olib
borilmoqda.
Ma'lumotlar tartiblangan bo'lsa ham, ikkilik qidiruv kerakli ma'lumotlarning
joylashuvidan foydalanmaydi.
Interpolyatsiya qidiruvida pozitsiyani tekshirish
Interpolatsiya qidiruvi indeksning o'rnini hisoblash orqali ma'lum bir
elementni topadi. Dastlab, element pozitsiyasi to'plamdagi eng o'rta elementning
pozitsiyasidir.
Agar mos kelsa, element indeksi qaytariladi. Ro'yxatni ikki qismga bo'lish
uchun biz quyidagi usuldan foydalanamiz:
mid = Lo + ((Salom - Lo) / (A [Salom] - A [Lo])) * (X - A [Lo])
qayerda -
A = ro'yxat
17](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_17.png)
![Lo = Ro'yxatning eng past indeksi
Salom = Ro'yxatning eng yuqori indeksi
A [n] = Ro'yxatdagi n indeksida saqlangan qiymat
Agar o'rta element elementdan kattaroq bo'lsa, u holda elementning holati
yana o'rta elementning o'ng tomonidagi pastki qatorda hisoblanadi. Aks holda,
element o'rta elementning chap tomonidagi pastki qatorda qidiriladi. Bu jarayon
pastki massiv uchun pastki qator nolga kamayguncha davom etadi.
Ishlash vaqtida interpolyatsiyani qidirish algoritmining murakkabligi qulay
vaziyatlarda n (log (log n)) va l (log n) ga teng.
Algoritm
Bu mavjud BST algoritmining improvizatsiyasi bo'lganligi sababli, biz
joylashishni aniqlash yordamida ma'lumotlar qiymatining "maqsadli" indeksini
topish bosqichlarini eslatib o'tamiz -
1-qadam - Ro'yxatning o'rtasidan ma'lumotlarni qidirishni boshlang .
2-qadam - Agar u mos keladigan bo'lsa, element indeksini qaytaring va chi-
qing.
3-qadam - Agar u mos kelmasa, pozitsiyani tekshiring.
4-qadam - Ro'yxatni tekshirish formulasidan foydalanib bo'ling va yangi o'r-
tani toping.
5-qadam - Agar ma'lumotlar o'rtadan kattaroq bo'lsa, yuqoriroq pastki ro'y-
xatda qidiring.
6-qadam - Agar ma'lumotlar o'rtadan kichikroq bo'lsa, pastki pastki
ro'yxatda qidiring.
7-qadam – Natija chiqgancha takrorlang.
Lug'atda so'z toping. Agar u "A" harfi bilan boshlansa, unda hech kim uni
o'rtadan qidirmaydi, balki lug'atni boshiga yaqinroq ochadi. Inson algoritmi va
boshqalar o'rtasidagi farq nima? Farqi shundaki, ikkilik qidiruv kabi algoritmlar
18](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_18.png)
![harakatga keltiradi. Har bir bosqichda oraliq o'lchamini ikki baravar kamaytirishni
kafolatlaydigan ikkilik qidiruvdan farqli o'laroq, noto'g'ri interpolyatsiya O( n )
ning samaradorligini kamaytirishi mumkin .
Yuqoridagi kodni har bir takrorlash taqqoslanganda besh olti marta ortiqcha
bir necha amallardan, ikkilik qidiruv algoritmi iteratsiyada boshiga bir taqqoslash
bilan yozilgan va faqat arzimas butun son arifmetikasidan foydalanishimiz
mumkin. Shunday qilib, u yigirmatadan ko'p bo'lmagan taqqoslashlar bilan million
elementlardan iborat massivni qidiradi (massiv elementlari saqlanadigan operativ
xotiraga kirishni o'z ichiga oladi) Buni engish uchun, yuqorida yozilganidek,
interpolyatsiya qidiruviga uchtadan ko'p bo'lmagan takrorlash ruxsat etiladi.
Interpolation search
function search( key : typekey; var r : dataarray ) : integer;
var high, j, low : integer;
begin
low := 1;
high := n;
while (r[high].k >= key) and (key > r[low].k) do
begin
j := trunc( (key-r[low].k) / (r[high].k-r[low].k) *
(high-low) ) + low;
if key > r[j].k then low := j+1
else if key < r[j].k then high := j-1
else low := j
end;
if r[low].k = key then search := low {*** found(r[low]) ***}
else search := -1; {*** notfound(key) ***}
24](/data/documents/06b4e30b-30f8-421f-be26-0d04a5e7d76a/page_24.png)
“INTERPOLATSION QIDIRUV ” MAVZUSIDA TAYYORLAGAN 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 III Xulosa ....................................................................................................27 IV Foydalanilgan adabiyotlar ...................................................................28 KURS ISHI
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. 2
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. Shunday qilib, ( ikkilik qidiruvda bo'lgani kabi ) massivning bir qismini bo'laklab olib, massivning kerakli elementiga bosqichma-bosqich erishiladi yoki qidiruv maydonining chegaralari shunday qiymatlarga toraytiriladi, ular ichida qidiradigan element yo'q bo‘lsa chegaralar orasidagi masofada massivdagi element topilmaganligini aytadi. Ko'rib turganingizdek, tsiklning o'zi unchalik murakkab emas. Interpolatsiya qidiruvi ikkilik qidiruvga biroz o'xshaydi . Faqat unda qidiruv maydoni ikkita teng qismga bo'linmaydi. Buning o'rniga, yangi qidiruv maydoni joriy element qiymati va qidiruv kaliti orasidagi masofaga qarab baholanadi. Interpolatsiyali qidiruv ikkilik qidiruvga qaraganda tezroq. Interpolyatsiya va ikkilik qidiruv o'rtasidagi yana bir muhim farq bu faqat raqamli qiymatlarni emas, balki matnli ma'lumotlarni qidirish qobiliyatidir. Interpolatsiya qidiruvi odatda ikkilik qidiruvdan samaradorlik jihatidan ustun bo'lib, o'rtacha log (log (N)) operatsiyalarini talab qiladi. Shunday qilib, uning 3
ishlash vaqti O (log (log (N))). Ammo, masalan, ketma-ketlik eksponent ravishda oshsa, tezlik O (N) ga oshadi, bu erda N (oldingi holatda bo'lgani kabi) ro'yxatdagi elementlarning umumiy soni. Algoritm elementlari bir-biriga nisbatan teng taqsimlangan ketma-ketlikda eng yuqori ko'rsatkichni ko'rsatadi. Shunday qilib, tsiklning o'zi oddiygina massivning maydonini formula bo'yicha hisoblab chiqadi, bu erda kerakli bo'lgan C ++ da o'xshashliklarni tanlab, ushbu interpolyatsiya printsipidan foydaladi. Interpolatsiya qidiruvi - kalitlarga tayinlangan raqamli qiymatlar (kalit qiymatlari) bo'yicha tartiblangan massivdagi kalitni topish uchun ishlatiladigan algoritmi. U birinchi marta 1957 yilda V. V. Peterson tomonidan tasvirlangan. Interpolatsiya qidiruvi odamlarning telefon kitobidan ismni izlash usuliga o'xshaydi ( kitobdagi yozuvlar buyurtma qilingan kalitning qiymati): har bir qadamda algoritm qolgan qidiruv maydonining qayerda joylashganligini hisoblab chiqadi. Qidiruv maydoni chegaralaridagi asosiy qiymatlarga va kerakli kalitning qiymatiga, odatda chiziqli interpolyatsiyaga asoslangan bo'lishi mumkin. Ushbu taxminiy pozitsiyada topilgan kalit qiymati keyin kerakli kalit qiymati bilan taqqoslanadi. Agar u teng bo'lmasa, taqqoslashga qarab, qolgan qidiruv maydoni taxminiy pozitsiyadan oldin yoki keyin bir qismga qisqartiriladi. Ushbu usul faqat asosiy qiymatlar orasidagi farqlar hajmini hisoblash to‘g‘ri bo'lsa ishlaydi. Taqqoslash uchun, ikkilik qidiruv har doim qolgan qidiruv maydonining o'rtasini tanlaydi, bir yoki boshqa yarmini tashlab, taxmin qilingan holatda topilgan kalit va kerakli kalit o'rtasidagi taqqoslashga qarab natija hosil qilinadi. O'rtacha interpolyatsiya qidiruvi taxminan (log (n)) taqqoslashlarini amalga oshiradi (agar ob'ektlar teng taqsimlangan bo'lsa), bu erda n - izlanadigan elementlar soni. Eng yomon holatda (masalan, tugmachalarning raqamli qiymatlari eksponent ravishda oshganida), O (n) gacha taqqoslash mumkin. Interpolyatsiya bilan ketma-ket qidiruvda siz qidirayotgan element yaqinidagi elementni topish uchun interpolyatsiya qo'llaniladi, so'ngra aniq elementni topish uchun chiziqli qidiruvdan foydalaniladi. 4
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. Turli xil ma'lumotlar to'plamlariga moslashish Agar ma'lumotlar to'plami uchun tartiblash kalitlari bir xil intervalda raqamlar bo'lsa, chiziqli interpolyatsiyani amalga oshirish oson va kerakli qiymatga juda yaqin indeks topadi. Boshqa tomondan, nom bo'yicha tartiblangan telefon kitobi uchun to'g'ridan- to'g'ri interpolatsiyani qidirish usuli qo'llanilmaydi. Biroq, xuddi shu yuqori darajadagi printsiplar hali ham qo'llanilishi mumkin: siz nomlardagi harflarning nisbiy chastotasidan foydalanib, telefon kitobidagi ismning o'rnini taxmin qilishingiz va uni nazorat nuqtasi sifatida ishlatishingiz mumkin. Bir xil kalit qiymatlarga ega seriyalar mavjud bo'lsa, ba'zi interpolatsiya qidiruv ilovalari kutilganidek ishlamasligi mumkin. Interpolatsiya qidiruvining eng oddiy amalga oshirilishi bunday ishga tushirishning birinchi (yoki oxirgi) elementini tanlashi shart emas. Telefon nomlarni qandaydir raqamga aylantirish aniq taqsimlangan raqamlarni keltirib chiqarmaydi (ismlarni saralash va ularni nom № 1, ism № 2 va hokazo deb atash kabi katta harakatlar bundan mustasno) va bundan tashqari, ba'zi 5