8-Amaliy ish

8-Amaliy ish

Qidiruv usullari: binar qidiruv, Fibonachchi qidiruv, binar daraxt bo’yicha qidiruv.

Qidiruv masalasi, qidruv usullari. Rеjа:

1. 
   Оddiy ko‟rib chiqish vа binаr izlаsh аlgоritmlаri
   
2. 
   Binаr dаrахtdа izlаsh аlgоritmlаri
   
3. 
   Rаqаmli izlаsh dаrахtlаri
   

Tayanch so‘z va iboralar: Algoritm tahlili. Boshlang„ich berilganlar sinflari. Eng yaxshi holat. Eng yomon holat.O„rtacha holat. O„sib borish bo„yicha saralash. Kamayish bo„yicha saralash. Ikkilik izlash .Ketma – ket izlash

Ma‟lumotlar ro„yxatidan kerakli axborotni izlash nazariy programmalashning fundamental masalalaridan biridir. Izlash algoritmlari to„g„risida gap ketganda axborot dasturdagi berilganlar massividan iborat bo„lgan yozuvlarda saqlanadi degan nuqtai nazardan kelib chiqiladi.Yozuvlar yoki ro„yhat elementlari massivda ketma-ket joylashadi. Ko„pincha yozuvlar bir necha sohalardan iborat bo„lishi mumkin, ammo izlashda ushbu sohalardan faqat bittasi(kalit) hisobga olinadi.Yozuvlar kalit sohasi qiymati bo„yicha saralangan yoki saralanagan bo„lishi mumkin.Saralangan ro„yxatda yozuvlar kalitning o„sib borish tartibida joylashgan bo„lib, saralanmagan ro„yxatda ular tasodifiy ravishda joylashadi.Saralanmagan ro„yxatdagi izlash jarayoni kerakli axborotga duch kelinmaguncha barcha yozuvlarni ko„rib chiqishdan iborat bo„ladi. Bu eng sodda izlash algoritidir. Konkret qiymatni izlash tanlash masalasi bilan bog„liq bo„lib, bunda qandaydir xususiyatga ega bo„lgan elementni topish talab etiladi. Masalan, kattalik bo„yicha beshinchi o„rindagi element, ro„yxat oxiridan yettinchi element yoki o„rtacha qiymatli element.

Ketma-ket izlash.Izlash algoritmlarida ro„yxatni maqsad elementi deb ataluvchi qandaydir konkret yelementni topishga qaratilgan ko„rib chtqish jarayoni amalga oshiriladi. Ketma-ket izlashda ro„yxat elementlari saralanmagan deb qabul qilinadi. Izlash jarayonida kerakli elementning ro„xatda mavjud ekanligi tekshirilibgina qolmay, balki ushbu kalitga bog„liq bo„lgan ma‟lumotlarga ham murojaat qilinadi.Masalan, kalitning qiymati xizatchining tartib nomeridan yoki boshqa identifikatordan iborat bo„lishi mukin. Kerakli kalit topilgandan so„ng dastur u bilan bog„liq ma‟lumotlarni o„zgartirishi yoki bosmaga chiqarishi mumkin. Umuman olganda, izlash algoritmining maqsadi kalitning pozitsiyasini (turgan joyini) aniqlashdan iborat. Agar kalit qiymat topilmasa, algoritm massivning yuqori chegarasidan katta bo„lgan indeks qiymatini chiqaradi. Ketma-ket izlash algoritmi ro„yhat elementlarini birinchi elementdan boshlab, keraklisi topilmagunga qadar birma-bir ko„rib chiqadi. Kalitning konkret qiymati ro„yxatda qanchalik uzoq joylashgan bo„lsa, izlashga shunchalik ko„p vaqt sarflanadi. Quyida ketma-ket izlash algoritmining ifodasini keltiramiz:
Ketma_ket_Izlash(list,target,N)
{list tekshiriluvchi ro„yxat}
{target izlanuvchi kalit}
{N ro„yxatdagi elementlar soni}
For i=l to N do if (target=list[i]) return i
end if end for return 0

Eng yomon holat tahlili.Ketma-ket izlash algoritmi ikki xil “eng yomon holat” variantiga ega. Birinchi holatda maqsad elementi ro„yxatda yeng oxirgi o„rinda joylashgan bo„ladi.

Ikkinchi holatda maqsad jlementi ro„yxatda avjud bo„lmaydi. Ushbu ikki holatda nechtadan taqqoslash amallari bajarilishini aniqlaymiz. Agar ro„yxat elementlari takrorlanmas deb faraz qilsak, ro„yxatning oxirgi elementiga yetgunga qadar algoritm N ta (ro„yxat N ta elementdan iborat) taqqoslashni bajaradi.
Xuddi shunga o„xshash tarzda maqsad elementi mavjud bo„lmagan ro„yxatda ham algoritm N ta taqqoslash amalini bajaradi.
O„rtacha holat tahlili.Izlash algoritmlari uchun ikkita o„rtacha holat bo„lishi mumkin. Birinchi holatda izlash jarayoni doimo muvaffaqiyatli tugaydi deb, faraz qilinadi. Ikkinchi holatda maqsad elementi mavjud bo„lmaydi. Agar maqsad elementi ro„yxatda mavjud bo„lsa, u mumkin bo„lgan N ta pozitsiyadan birini egallaydi. Uning bu pozitsiyalardan har birini egallash ehtimoli bir xil deb hisoblasak, bu ehtimol 1/N ga teng. N ta holatdan har bittasi uchun algoritmning bajaradigan taqqoslashlari soni izlanuvchi element tartibi bilan mos tushadi. Natijada o„rtacha holatdagi murakkablik uchun quyidagi tenglikka ega bo„lamiz:

𝑁
A⁽𝑛⁾ = ¹ ∑ i
𝑁
i=1
1 𝑁(𝑁 + 1)
⁼ 𝑁 2
₌ 𝑁 + 1
2

Agar ro„yxatda izlanuvchi element mavjud bo„lmagan holni oladigan bo„lsak, ko„rib chiqishlar soni
N +1 taga ortadi. Izlanuvchi element mavjud bo„lmaganda taqqoslashlar soni N ga teng bo„lganligidan va N ta imkoniyat ehtimoli bir xil deb olinsa, quyidagiga ega bo„linadi:

A⁽𝑛⁾ = ¹
𝑁 + 1
𝑁
(∑ i + 𝑁) = ¹
𝑁 + 1
i=1
𝑁
∑ i + ¹
𝑁 + 1
i=1
_{𝑁 ≈} 𝑁 + 2
2

( N juda katta bo„lganda l/(N + 1) qiymat 0 ga yaqinlashadi.)

Bundan izlanuvchi elementning ro„yxatda mavjud bo„lmasligi holati hisobga olinganda o„rtacha holat murakkabligi ½ ga teng miqdorda oshishi mumkinligi ko„rinadi.
Ikkilik izlash.Saralangan massivda biror elementni izlash jarayonida maqsad elementni massiv o„rtasidan olingan element bilan taqqoslaganda 3 ta holatdan biri yuz beradi: qiymatlar teng; maqsad element kichik; maqsad element katta. Birinchi holat eng yaxshi hisoblanib, izlash jarayoni to„xtaydi. Qolgan ikkila holatda ham massivning yarmini tashlab yuborish mumkin.Maqsad qiymat o„rtanchi elementdan kichik bo„lsa, u ro„yxatda o„rtancha elementdan oldin keladi, aks holda ushbu elementdan keyin keladi.Shu jarayonni davom ettirib, qro„yxatning qolgan qisining ha yarini tashlab yuboraiz va hokazo. Natijada quyidagiga ega bo„lamiz:
Ikkilik_ket_Izlash(list,target,N list spisok dlya prosmotra target selevoye znacheniye
N chislo elementov v spiske start=1
end=N
while start<=end do select(compare(list[middle),target))from case 1: start=middle+l
case 0: return middle case 1: end=middle l end select
end while return 0

ushbu algoritmda start o„zgaruvchisiga middle o„zgaruvchisiga nisbatan 1 ga ortiq qiymat o„zlashtiriladi, agar maqsad qiymat topilgan o„rtacha element qiymatidan katta bo„lsa. Agar maqsad element qiymati o„rtacha element qiymatidan kichik bo„lsa, end o„zgaruvchisiga middle o„zgaruvchisiga nisbatan 1 taga kam qiymat o„zlashtiriladi. Bunda sikl qanday ishlaydi?Agar maqsad element topilsa, return operatori ishlaydi va sikl to„xtatiladi. Agar maqsad element topilmasa, har bir sikl iteratsiyasida start o„zgaruvchisining qiymati ortadi yoki end o„zgaruvchisining qiymati kamayadi. Bu ikki o„zgaruvchining qiymatlari bir-biriga yaqinlashib boradi.Qaysidir qadamda bu ikki o„zgaruvchining qiymati tenglashib, start=end=middle sharti uchun ham sikl yana bir marta bajariladi. Shundan so„ng ushbu indeksli element maqsad element bo„lmasa, start ning qiymati middle va endga nisbatan 1 ga oshadi yoki aksincha end ning qiymati middle va start ga nisbatan 1 ga kamayadi. Ikki holatda ham while operatorining sharti yolg„on qiymat qabul qilib, sikl to„xtatiladi.
O„rtacha holat tahlili. O„rtacha holatni tahlil etishda ikki imkoniyat ko„rib chiqiladi:maqsad elementning ro„yxatda mavjud bo„lgan holat; maqsad elementning ro„yxatda mavjud bo„lmaslik holati. Birinchi holatda N ta imkoniyat mavjud va ularning barchasi teng kuchli l/N ehtimolga ega. Bunda bajariladigan taqqoslashlarning binar daraxtidan foydalanib, quyidagi formulalarga ega bo„lamiz:
𝑘
A⁽𝑛⁾ = ^{1 1} ∑ i 2ⁱ (𝑁 = 2^𝑘 − 1)
𝑁 2
i=1
Ushbu formulalarni qisqartirilgan holda yozsak, quyidagi ko„rinishni oladi:
A⁽𝑛⁾ = ^{𝑘𝑁 + 𝑘} − 1
𝑁
N qiymati ortib borgan sari ^𝑘 qiymat 0 ga yaqinlashib boradi va
𝑁
A⁽𝑛⁾ ≈ log₂(𝑁 + 1) − 1 ga ega bo„lamiz.
Иккинчи ҳолатни, яъни мақсад элементнинг рўйхатда мавжуд бўлмаслик ҳолатини кўриб чиқадиган бўлсак, изланган элементнинг рўйхатдаги мумкин бўлган позициялари сони N га тенг, аммо яна N + 1 та рўйхатдан ташқаридаги имкониятлар сони ҳам мавжуд. Икониятлар сони N + 1 га тенг, чунки мақсад элеент ршйхатдаги биринчи элементдан кичик, биринчидан катта, амо иккинчидан кичик, иккинчидан катта, аммо учинчидан кичик ва ҳоказо токи мақсад қиймат N-элементлан катта бўлгунга қадар.Ҳар бир ҳолатда изланувчи элементнинг рўйхатда мавжуд эмаслиги k та таққослаш бажарилгандан кейин маълум бўлади. Ҳисоблашларда ҳамаси бўлиб,
2N +1 та имконият кўриб чиқилади. Шундай қилиб, қуйидагига эга бўламиз:

A⁽𝑛⁾ = ¹
2𝑁 + 1
𝑘
(∑ i 2ⁱ⁻¹ + (N + 1)k) ≈ log₂ i=1
(𝑁 + 1) − ¹
2

(𝑁 = 2^𝑘 − 1)

Tanlash algoritmi

Ba‟zi holatlarda bizga ro„yxatdagi konkret qiymatga ega bo„lgan elementni emas, balki boshqa xususiyatga ega bo„lgan elementni izlashga to„g„ri keladi. Masalan, yozuv sohalarining kattalik bo„yicha k-o„rinda turgan qiymatini topish talab etilsin. Bunday yozuvni topishning usullaridan biri ro„yxatni kamayish tartibidan saralashdan iborat; bunda kattaliu bo„yicha k-yozuv k-o„ringa joylashtiriladi. Bu usul keragidan ko„proq mehnat talab qiladi: chunki izlangandan kichik bo„lgan elementlar bizni qiziqtirmaydi.Bu vaziyatdan chiqishning yana bir usuli mavjud: ro„yxatdan eng katta element topilib, ro„yxatning oxiriga joylashtiriladi.So„ngra ro„yxat qolgan qismining eng katta elementi topiladi va ro„yxat oxiridan ikkinchi o„ringa joylashtiriladi. Ushbu protsedurani K marta takrorlab, kattalik bo„yicha K-o„rinda turuvchi elementni topib olamiz: Tanlash(list,K,N)

List ro„yxat o„zgaruvchisi N ro„yxat elementlari soni K kattalik bo„yicha tartib For i=1 to K do Largest=list[1] LargestLocation=1
For i=2 to N-(i-1) do If list[i]>largest then LargestLocation=j End if
End for
Swap(list[N-(i-1),list[LargestLocation]) End for
Return largest
Ushbu algoritmning murakkabligi qanday? Har bir o„tishda largest o„zgaruvchisiga ro„yxat birinchi elementi qiymatini o„zlashtirib, so„ngra bu o„zgaruvchi qolgan elementlar bilan taqqoslanadi.Birinchi o„tishda N -1 taqqoslash, ikkinchi o„tishda bittaga kam (N -2) ta taqqoslash va hokazo K-o„tishda N - K taqqoslashlar bajariladi.Shuning uchun kattalik bo„yicha K-o„rindagi eleyentni izlash uchun
𝐾
∑(𝑁 − i) = 𝑁𝐾 − ^{𝐾(𝐾 − 1)}
2
i=1
ta taqqoslashlar bajariladi.Shuni eslatib o„tish lozimki, K N /2 dan katta bo„lsa, izlashni ro„yxat
oxiridan boshlagan ma‟qul. K ning 1 yoki N ga yaqin qiymatlari uchun ushbu algoritm anchagina eqqektiv hisoblansa, ro„yxat o„rtasidagi qiyatlar uchun yanada unumdor algoritmlar mavjud.Bizga faqat kattalik bo„yicha K-tartibli element kerak bo„lgani uchun izlangan elementdan katta elementlarning o„rni bizni qiziqtirmaydi. Ro„yxatdan olingan har bir element uchun ro„yxat ikki qismga ajraladi: berilgan elementdan kattalari va kichiklari.Ro„yxat elementlarini tanlangan elementdan oldin faqat undan kichiklari,keyin esa faqat undan kattalari joylashadigan qilib, qayta saralasak, shu bilan birga tanlangan element R-o„rinda joylashsa, uning kattalik bo„yicha R-element ekanligi aniqlanadi.Ro„yxatni bunday qayta saralash tanlangan elementni qolganlari bilan taqqoslab chiqishni talab etadi. Bunda R- 1 taqqoslash bajariladi. Ushbu rekursiv algoritm quyidagi ko„rinishga ega: