|
Qidiruv algoritmlari va ularni optimallashtirishBog'liq INFORMACIYANÍ QORǴAWDÍ SHÓLKEMLESTIRIW HÁM PROGRAMMALÍQ QURALLARÍis (3), Elektronikadan slayd jumisi, 4-курс АХ Кундузги, 2-Лекция (1), BAXTIYAR Tarmoq xavfsizligi, Ismailov Asror 7.8.9, 7-MA\'RUZA, Tu\'rli xaliqlar kesteshiligi (2), 1. Ilmiy loyiha, УР ВИНСЕРВЕР ЛАБ 5, ta lim jarayonida infografika texnologiyasining o rni va uning ishlab, Astronomiya(2013), Xakimova Navruza 304-19 DI 5-lab, Sardorbek mustaqil ish, 3 томонлома шартнома битирувчи уз
Proceedings of International Conference on Educational Discoveries and Humanities
Hosted online from Plano, Texas, USA.
Date: 1
st
November, 2022
ISSN: XXXX-XXXX Website: econferenceseries.com
214 |
P a g e
chiqadiki, kalit qiymati ro‘yxatda qancha uzoqda turgan bo‘lsa, qidiruv shuncha
uzoq davom etadi (vaqtga nisbatan). Bu holatni ketma-ket qidiruv algoritmi tahlilida
e‘tiborga olish zarur bo‘ladi.
Ketma-ket qidiruv algoritmining to‘liq ko‘rinishi quyidagicha:
SequentialSearch (list, target,N)
list // qidirish amalini bajarish uchun ro‘yxat
target //kalit qiymati
N
//ro‘yxatdagi elementlar soni
for i=1 to N do
if (target=list[i]) return
i
end if end
for return 0
Algoritmning tahlili. Ketma-ket qidiruv algoritmida ikki eng yomon holat mavjud.
Birinchi holatda qidiruvdagi element ro‘yxat oxirida joylashgan bo‘ladi. Ikkinchi
holatda esa, qidiruvdagi element ro‘yxatda mavjud bo‘lmaydi. Har ikki holatda ham
necha marta taqqoslash amali bajarilishini qarab chiqamiz. Ro‘yxat elementlarining
kalit qiymati unikal (takrorlanmas) deb qaraydigan bo‘lsak, qidiruvdagi elementga
moslik oxirgi yozuvda uchrasa, u holda oxirgi taqqoslash keraksiz bo‘lishi mumkin.
Lekin algoritm oxirgi elementga qadar taqqoslash amalini bajaradi. Natijada N ta
taqqoslash amalga oshiriladi (bu yerda N- ro‘yxatdagi elementlar soni).
Qidirilayotgan qiymatning ro‘yxatda yo‘qligini tekshirish uchun uni ro‘yxatning
barcha elementlari bilan taqqoslab chiqishga to‘g‘ri keladi. Agar biror element bilan
taqqoslash qoldirilsa, u holda qidirilayotgan element rostdan ham ro‘yxatda
yo‘qligini aniqlab bo‘lmaydi. Bu esa ro‘yxatning barcha elementlarini qarab
chiqishni talab etadi va bu holatda ham N marta taqqoslash amalga oshiriladi.
Umuman olganda, qidirilayotgan element ro‘yxatning oxirgi elementi yoki unda
mavjud emasligini aniqlash uchun N marta taqqoslash amali bajariladi. N har qanday
qidiruv algoritmining eng yuqori chegarasi hisoblanadi, agar taqqoslashlar N dan
ko‘p bajarilsa, hech bo‘lmaganda ro‘yxatning bitta elementi bilan ikki marta
taqqoslash bajarilganligini bildiradi. Bundan kelib chiqadiki, ortiqcha ish bajarilgan
va algoritmni yaxshilash talab etiladi.
|
| |
