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:
( )
∑
( )
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:
( )
(∑
)
∑
( 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:
( )
∑
(
)
Ushbu formulalarni qisqartirilgan holda yozsak, quyidagi ko„rinishni oladi:
( )
N qiymati ortib borgan sari
qiymat 0 ga yaqinlashib boradi va
( )
( )
ga ega bo„lamiz.
Иккинчи ҳолатни, яъни мақсад элементнинг рўйхатда мавжуд бўлмаслик ҳолатини кўриб
чиқадиган бўлсак, изланган элементнинг рўйхатдаги мумкин бўлган позициялари сони N
га тенг, аммо яна N + 1 та рўйхатдан ташқаридаги имкониятлар сони ҳам мавжуд.
Икониятлар сони N + 1 га тенг, чунки мақсад элеент ршйхатдаги биринчи элементдан
кичик, биринчидан катта, амо иккинчидан кичик, иккинчидан катта, аммо учинчидан
кичик ва ҳоказо токи мақсад қиймат N-элементлан катта бўлгунга қадар.Ҳар бир ҳолатда
изланувчи элементнинг рўйхатда мавжуд эмаслиги k та таққослаш бажарилгандан кейин
маълум бўлади. Ҳисоблашларда ҳамаси бўлиб,
2N +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
∑(
)
( )
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:
Do'stlaringiz bilan baham: |