Fibonacci and interpolision search Fibonacci search - Fibonachchi qidiruvi tartiblangan massivdagi elementni qidirish uchun Fibonachchi raqamlaridan foydalanadigan taqqoslashga asoslangan usuldir. n o‘lchamdagi saralangan massiv arr[] va unda izlanadigan x elementi berilgan. X ning qaytish indeksi, agar u massivda bo'lsa, aks holda -1 qaytariladi.
Misollar: - Kirish: arr[] = {2, 3, 4, 10, 40}, x = 10 Chiqish: 3 x elementi 3-indeksda mavjud.
- Kirish: arr[] = {2, 3, 4, 10, 40}, x = 11 Chiqish: -1 x elementi mavjud emas.
Maʼlumot - Fibonachchi raqamlari rekursiv ravishda F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1 sifatida aniqlanadi. Fibonachchi raqamlarining dastlabki bir nechtasi 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
- Quyidagi kuzatuv diapazonni yoʻq qilish uchun va shuning uchun O(log(n)) murakkabligi uchun ishlatiladi.
F(n - 2) &taxminan; (1/3)*F(n) va F(n - 1) &taxminan; (2/3)*F(n). Algorithm - Qidirilayotgan element x bo'lsin. G'oya birinchi navbatda berilgan massiv uzunligidan katta yoki unga teng bo'lgan eng kichik Fibonachchi raqamini topishdir. Topilgan Fibonachchi soni fib bo'lsin (Fibonachchi soni). Indeks sifatida biz (m-2)-chi Fibonachchi raqamidan foydalanamiz (agar u to'g'ri indeks bo'lsa). (m-2)' Fibonachchi soni i bo'lsin, arr[i] ni x bilan solishtiramiz, agar x bir xil bo'lsa, i ni qaytaramiz. Aks holda, agar x katta bo'lsa, biz i dan keyin pastki qator uchun takrorlaymiz, aks holda biz i dan oldin pastki qator uchun takrorlaymiz. Quyida toʻliq algoritm berilgan : arr[0..n-1] kirish massivi va izlanadigan element x boʻlsin.
- 1.n dan katta yoki teng eng kichik Fibonachchi sonini toping. Bu raqam fibM [m'th Fibonachchi raqami] bo'lsin. Undan oldingi ikkita Fibonachchi raqami fibMm1 [(m-1)'-chi Fibonachchi raqami] va fibMm2 [(m-2)'-chi Fibonachchi raqami] bo'lsin.
- 2.Massivda tekshirilishi kerak bo'lgan elementlar bo'lsa:
- 2.1 x ni fibMm2 qamrab olgan diapazonning oxirgi elementi bilan solishtiring.
2.2 Agar x mos kelsa, indeksni qaytaring. - 2.3.Aks holda, agar x elementdan kichik bo'lsa, uchta Fibonachchi o'zgaruvchisini ikkita Fibonachchi pastga siljiting, bu qolgan massivning taxminan orqa uchdan ikki qismini yo'q qilishni ko'rsatadi.
- 2.4 Aks holda, x elementdan katta bo'lsa, uchta Fibonachchi o'zgaruvchisini bir Fibonachchi pastga siljiting. Ofsetni indeksga qaytaring. Bular birgalikda qolgan massivning oldingi uchdan bir qismini yo'q qilishni ko'rsatadi.
- 3.Taqqoslash uchun bitta element qolishi mumkinligi sababli, fibMm1 1 ekanligini tekshiring. Ha bo'lsa, x ni qolgan element bilan solishtiring. Agar mos kelsa, indeksni qaytaring.
- Tasvir: Keling, quyidagi misol bilan algoritmni tushunamiz:
- Tasviriy taxmin: 1-asoslangan indekslash. Maqsadli element x - 85. Massivning uzunligi n = 11. 11 dan katta yoki unga teng boʻlgan eng kichik Fibonachchi soni 13. Rasmimizga koʻra, fibMm2 = 5, fibMm1 = 8 va fibM = 13. Boshqa bir amalga oshirish detali ofset oʻzgaruvchisidir. (nol bilan boshlangan). Old tomondan boshlab, yo'q qilingan diapazonni belgilaydi. Biz uni vaqti-vaqti bilan yangilab turamiz. Endi ofset qiymati indeks bo'lgani uchun va barcha indekslar, shu jumladan uning ostidagi va undan pastroq indekslar olib tashlanganligi sababli, unga biror narsa qo'shish mantiqan. fibMm2 massivimizning taxminan uchdan bir qismini belgilaganligi sababli, shuningdek, u belgilagan indekslar ham haqiqiy bo'lishi aniq, biz elementni i = min(ofset + fibMm2, n) indeksida ofset qilish va tekshirish uchun fibMm2 qo'shishimiz mumkin.
INTERPOLISION SEARCH n ta teng taqsimlangan qiymatlardan iborat saralangan massiv berilgan arr[], massivda ma’lum bir x elementni qidirish funksiyasini yozing. Chiziqli qidiruv elementni O(n) vaqtida topadi, Jump Search O(√ n) vaqtni oladi va Binary Search O(log n) vaqtni oladi. Interpolatsiya qidiruvi ikkilik qidiruvga nisbatan yaxshilanishdirmisol uchun, tartiblangan massivdagi qiymatlar bir xilda taqsimlangan. Interpolatsiya ma'lum ma'lumotlar nuqtalarining diskret to'plami oralig'ida yangi ma'lumotlar nuqtalarini yaratadi. Ikkilik qidiruv har doim tekshirish uchun o'rta elementga o'tadi. Boshqa tomondan, interpolatsiya qidiruvi qidirilayotgan kalitning qiymatiga qarab turli joylarga borishi mumkin. Misol uchun, agar kalitning qiymati oxirgi elementga yaqinroq bo'lsa, interpolatsiya qidiruvi oxirgi tomonda qidirishni boshlashi mumkin. Algorithm - Interpolatsiya algoritmining qolgan qismi yuqoridagi bo'lim mantiqidan tashqari bir xil. 1- qadam: Loopda prob pozitsiyasi formulasidan foydalanib, "pos" qiymatini hisoblang. 2- qadam: Agar u mos keladigan bo'lsa, element indeksini qaytaring va chiqing. 3-qadam: Agar element arr[pos] dan kichik bo'lsa, chap pastki massivning prob o'rnini hisoblang. Aks holda, o'ng pastki qatorda xuddi shunday hisoblang. 4-qadam : Moslik topilmaguncha yoki pastki massiv nolga tushguncha takrorlang.
- Vaqt murakkabligi: o'rtacha holat uchun O(log 2 (log 2 n)) va eng yomon holat uchun O(n)
Do'stlaringiz bilan baham: |
