logo

Eng katta qismiy ketma-ketlikni qidirish

Загружено в:

12.08.2023

Скачано:

0

Размер:

186.408203125 KB
“Eng katta qismiy ketma-ketlikni qidirish”
MUNDARIJA
 KIRISH. .......................................................................................................... 2
I Qismiy ketma-ketlikni qidirish ..................................................................... 3
1.1 Ketma-ket qidiruv algoritmi .................................................................. 3
1.2 Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi ......................... 5
1.3 Dastur kodi: ........................................................................................... 6
1.4 Indeksli ketma-ket qidiruv algoritmi. .................................................... 9
II. Qismiy ketma-ketlikni qidirish uchun Knut Morris Pratt algoritmi ......... 12
2.1 Knut Morris Pratt algoritmi haqida ..................................................... 12
2.2 Patterndan DFA yasash: ...................................................................... 14
2.3 Knuth-Morris-Pratt algoritmini kodda ifodalash ................................. 15
 III. Deykstra algoritmi .................................................................................. 20
XULOSA ....................................................................................................... 22
FOYDALANILGAN ADABIYOTLAR ....................................................... 24   KIRISH.
Algoritm   tushunchasi   zamonaviy   matematika   va   informatikaning   asosiy
tushunchalaridan   biri   hisobanadi.     Algoritm   ma’lum   bir   turga   oid   masalalarni
yechishda   ishlatiladigan   amallarning   muayyan   tartibda   bajarilishi   haqidagi   qoida
hisoblanadi.
    “Qismiy   ketma-ketlikni   qidirish”   asosan,   algoritmda   bu   mavzuni
yoritishimizda   qidiruv   nima   ekanligiga   to’xtalib   o’tsak.   Ma’lumotlarni   qidirish
algoritmlari   bu-   to’plam   ma’lumotlar   orasidan   ma’lum   bir   kalit   so’zga   mos
keluvchi   elimentlarni   qidirishga   aytiladi.   Ma’lumotlarni   qidirish   algoritmlari
odatda ikki toifaga bo’linadi va bular quydagilar: 
Tarkibiy qidiruv: Bunda ro’yxat yoki qator ketma- ket o’tkaziladi va har bir
eliment   tekshiriladi.   Bunga   misol   sifatida   chiziqli   qidiruvni   keltirsak   bo’ladi.
Qidirish   algoritmining   eng   soddasi   bo’lgan   chiziqli   qidirish   algoritmi,   chiziqli
ma’lumotlar tuzulmalaridan biror bir shart yoki qiymat bo’yicha eliment qidirishga
mo’ljallangan   va   uning   algoritmik   murakkabligi   quydagicha:   Chiziqli   qidirish
algoritmining   vaqt   bo’yicha   murakkabligi   uning   nomidan   ham   ma’lum,   ya’ni
chiziqli   O(n).   Ya’ni,   eng   yomon   holat   sifatida   eliment   array   bo’lmagan   holat
qaraladi va bunda algoritm maximum n ta qadam ish bajarishi kerak bo’ladi. 
Intervalli   qidirish-   bu   algoritmar   maxsus   ajratilgan   ma’lumotlar
tuzilmalarida   qidirish   uchun   mo’ljallangan.   Ushbu   turdagi   qidiruv   algoritmlari
Linear   Search-ga   qaraganda   ancha   samaralidir,   chunki   ular   qayta-qayta   qidiruv
tuzulmasi   markaziga   yo’naladi   va   qidiruv   maydonini   ikkiga   bo’ladi.   Masalan:
Ikkilik qidiruv.
Ikkilik   qidiruv-   bu   algoritmi   asosan   to’plamni   ikkiga   bo’lishlar   orqali
qidirishdan   iborat.   Ya’ni   unda   bo’linishlar   toki   kalit   so’z   topulmaganicha   davom
etadi.
2 I Qismiy ketma-ketlikni  qidirish
Kompyuterda   ma’lumotlarni   qayta   ishlashda   qidiruv   asosiy   amallardan
biri     hisoblanadi.     Uning     vazifasi     berilgan     argument     bo’yicha     massiv
ma’lumotlari     ichidan     mazkur     argumentga     mos     ma’lumotlarni     topish     yoki
bunday     ma’lumot     yo’qligini     aniqlashdan     iborat.     Ixtiyoriy     ma’lumotlar
majmuasi  jadval  yoki  fayl  deb  ataladi.
Ixtiyoriy   ma’lumot   (yoki   tuzilma   elementi)   boshqa   ma’lumotdan   biror
bir   belgisi    orqali   farq   qiladi.   Mazkur   belgi   kalit   deb   ataladi.   Kalit   noyob
bo’lishi,     ya’ni     mazkur     kalitga     ega     ma’lumot     jadvalda     yagona     bo’lishi
mumkin.     Bunday     noyob     kalitga     boshlang’ich     (birinchi)     kalit     deyiladi.
Ikkinchi     kalit     bir     jadvalda     takrorlansada     u     orqali     ham     qidiruvni     amalga
oshirish     mumkin.    Ma’lumotlar     kalitini     bir     joyga    yig’ish     (boshqa     jadvalga)
yoki  yozuv  sifatida  ifodalab  bitta  maydonga  kalitlarni  yozish  mumkin.  Agar
kalitlar  ma’lumotlar  jadvalidan  ajratib  olinib  alohida  fayl  sifatida  saqlansa,  u
holda  bunday  kalitlar  tashqi  kalitlar  deyiladi.  Aks  holda,  ya’ni  yozuvning  bir
maydoni     sifatida     jadvalda     saqlansa     ichki     kalit     deyiladi.     Kalitni     berilgan
argument    bilan   mosligini    aniqlovchi   algoritmga   berilgan   argument   bo’yicha
qidiruv   deb   ataladi.   Qidiruv   algoritmi   vazifasi   kerakli   ma’lumotni   jadvaldan
topish     yoki     yo’qligini     aniqlashdan     iboratdir.     Agar     kerakli     ma’lumot     yo’q
bo’lsa,  u  holda  ikkita  ishni  amalga  oshirish  mumkin:
1.   Ma’lumot yo’qligini indikatsiya qilish  (belgilash)
2.   Jadvalga ma’lumotni qo’yish.
Faraz qilaylik,  k  –  kalitlar  massivi.  Har  bir  k(i)  uchun  r(i)  –  ma’lumot
mavjud.     Key   –     qidiruv     argumenti.     Unga     rec     -     informatsion     yozuv     mos
qo’yiladi.  Jadvaldagi  ma’lumotlarning  tuzilmasiga  qarab  qidiruvning  bir  necha
turlari  mavjud.
1.1 Ketma-ket  qidiruv  algoritmi
Mazkur     ko’rinishdagi     qidiruv     agar     ma’lumotlar     tartibsiz     yoki     ular
tuzilishi     noaniq     bo’lganda     qo’llaniladi.     Bunda     ma’lumotlar     butun     jadval
bo’yicha     operativ     xotirada     kichik     adresdan     boshlab,     to     katta     adresgacha
ketma-ket  qarab  chiqiladi.
Massivda  ketma-ket  qidiruv  (search  o’zgaruvchi  topilgan  element  tartib
raqamini  saqlaydi).
3 Ketma-ket  qidiruv  algoritmi  C++  tilida  quyidagicha  bo’ladi:
int  qidiruv(int  key)
{  for  (int  i=0;i<n;i++)<  p=""></n;i++)<>
if  (k[i]==key)  {  search  =  i;return  search;}
search  =  -1;
return  search;
}
}
Massivda   ketma-ket     qidiruv     algoritmi     samaradorligini     bajarilgan
taqqoslashlar     soni    M     bilan     aniqlash    mumkin.    M
min     =    1,    M
max     =    n.    Agar
ma’lumotlar     massiv     yacheykasida     bir     xil     ehtimollik     bilan     taqsimlangan
bo’lsa,   u   holda   M
o’rt         (n   +   1)/2   bo’ladi.   Agar    kerakli   element    jadvalda
yo’q  bo’lib,  uni  jadvalga  qo’shish  lozim  bo’lsa,  u  holda  yuqorida  keltirilgan
algoritmdagi  oxirgi  ikkita  operator  quyidagicha  almashtiriladi .
n=n+1;
          k[n-1]:=key;
r[n-1]:=rec;  search:=n-1;
return  search;
Agar     ma’lumotlar     jadvali     bir     bog’lamli     ro’yhat     ko’rinishida     berilgan
bo’lsa  ,  u  holda  ketma-ket  qidiruv  ro’yhatda  amalga  oshiriladi.
1-Rasm
Chiziqli  bir  bog’lamli  ro’yhatdan  key  kalitga  mos  elementni  ketma-ket
qidiruv  usuli  yordamida  izlab  topish  dasturi.
Node  *q=NULL;
Node  *p=lst;
while  (p  !=NULL){
4 if  (p->k  ==  key){  search  =  p;
return  search;
}
q  =  p;
p  =  p->nxt;   
}
Node  *s=new  Node;;
s->k=key;
s->r=rec;
s->nxt=  NULL;
if  (q  ==  NULL){  s->nxt=lst;  lst  =  s;
} 
 else  q->nxt  =  s;
search=  s;
return  search;
Ro’yhatli   tuzilmaning     afzalligi     shundan     iboratki,     ro’yhatga     elementni
qo’shish     yoki     o’chirish     tez     amalga     oshadi,     bunda     qo’shish     yoki     o’chirish
element     soniga     bog’liq     bo’lmaydi,     massivda     esa     elementni     qo’shish     yoki
o’chirish  o’rta   hisobda  barcha  elementlarning  yarmini   siljitishni  talab  qiladi.
Ro’yhatda     qidiruvning     samaradorligi     taxminan     massivniki     bilan     bir     xil
bo’ladi.
1.2 Teng  bo’lish  orqali  qidiruv  (ikkilik  qidiruv)  algoritmi
Faraz     qilaylik,     o’sish     tartibida     tartiblangan     sonlar     massivi     berilgan
bo’lsin.  Ushbu  usulning  asosiy  g’oyasi  shundan  iboratki,  tasodifiy  qandaydir
A
M     element     olinadi     va     u     X     qidiruv     argumenti     bilan     taqqoslanadi.     Agar
A
M =X   bo’lsa,    u   holda   qidiruv   yakunlanadi;    agar    A
M    >X   bo’lsa,    u   holda
indekslari  M  dan  katta  bo’lgan  barcha  elementlar  kelgusi  qidiruvdan  chiqarib
yuboriladi.
5 M     ixtiyoriy     tanlanganda     ham     taklif     qilinayotgan     algoritm     korrekt
ishlaydi.     Shu     sababali     M     ni     shunday     tanlash     lozimki,     tadqiq     qilinayotgan
algoritm  samaraliroq  natija  bersin,  ya’ni  uni  shunday  tanlaylikki,  iloji  boricha
kelgusi   jarayonlarda   ishtirok   etuvchi   elementlar   soni   kam   bo’lsin.   Agar   biz
o’rtacha     elementni,     ya’ni     massiv     o’rtasini     tanlasak     yechim     mukammal
bo’ladi.     Misol     uchun     butun     sonlardan     iborat,     o’sish     bo’yicha     tartiblangan
massivdan  ikkilik  qidiruv  usuli  yordamida  key  kalitga  mos  elementni  izlash
dasturini  ko’rib  chiqamiz.
1.3 Dastur  kodi:
#include  <iostream>
using   namespace std ;
int  main(){
int  n;cout<<"n=";cin>>n;
int  k[n];
for(int  i=0;i>k[i];
int  key,  search;
cout<<"qidirilayotgan  elementni  kiriting=";cin>>key;
int  low  =  0;
while  (low  <=  hi){
int  mid  =  (low  +  hi)  /  2;j++;
if  (key  ==  k[mid]){
search  =  mid;
cout<<"qidirilayotgan     element     "<<search+1<<"     o’rinda=""     turibdi=""
va=""     u=""     "<<j<<"=""     ta=""     solishtirishda=""     toplidi\n";<=""
p=""></search+1<<">
system("pause");
exit(0);
}
if  (key  <  k[mid])
hi  =  mid  -  1;
6 else  low  =  mid  +  1;
} 
 search=-1;
cout<<j<<"     ta=""     solishtirish=""     amalga=""     oshirildi=""     va=""
qidirilayotgan=""  element=""  topilmadi\n";<=""  p=""></j<<">
system("pause");  }
Dastur  natijasi:
n=6
1  2  3  4  5  6
qidirilayotgan  elementni  kiriting=6
qidirilayotgan  element  6  o'rinda  turibdi  va  u  3  ta  solishtirishda  toplidi
Qidiruv  jadvalini  qayta  tartibga  keltirish
Umuman     olganda,     jadvalda     har     bir     elementni     qidirish     ehtimolligini
qandaydir     bir     qiymat     bilan     izohlash     mumkin.     Faraz   qilaylik     jadvalda
qidirilayotgan     element     mavjud.     U     holda     qidiruv     amalga     oshirilayotgan
jadvalni     diskret     holatga     ega     tizim     sifatida     qarash     mumkin     hamda     unda
qidirilayotgan  elementni  topish  ehtimolligi  –  bu  tizim  i-chi  holati  ehtimolligi
p(i)  deb  olish  mumkin.
2-Rasm
Jadvalni  diskret  tizim  sifatida  qaraganimizda,  undagi  taqqoslashlar  soni
diskret  tasodifiy  miqdorlar  qiymatlarini  matematik  kutilmasini  ifodalaydi.
Z=Q=1*p(1)+2*p(2)+3*p(3)+…+n*p(n)
Ma’lumotlar  jadvalda  quyidagi  ko’rinishda  tartiblangan  bo’lishi  lozim:
p(1)  p(2)    p(3)    …  p(n).
7 Bu     shart     taqqoslashlar     sonini     kamaytirib,     samaradorlikni     oshiradi.
Sababi, ketma-ket  qidiruv  birinchi  elementdan  boshlanganligi  uchun  eng  ko’p
murojaat  qilinadigan  elementni  birinchiga  qo’yish  lozim.
Qidiruv     jadvalini     qayta     tartibga     keltirishning     eng     ko’p     ishlatiladigan
ikkita  usuli  mavjud.  Ularni  bir  bog’lamli  ro’yhatlar  misolida  ko’rib  chiqamiz.
1.     Topilgan     elementni     ro’yhat     boshiga     qo’yish     orqali     qayta     tartibga
keltirish.
2.   Transpozitsiya  usuli.
Topilgan     elementni     ro’yhat     boshiga     qo’yish     orqali     qayta     tartibga
ketirish.
3-Rasm   
Topilgan   element   birdaniga   ro’yhat     boshiga     joylashtiriladi.     Tuzilmadan
har   safar     birorta     element     izlab     topilsa     va     u     ro’yhat     boshiga     olib     borib
qo’yilaversa,     natijada     oxirgi     izlangan     elementlar     ro’yhat     boshiga     joylashib
qoladi     va     biz     oxirgi     vaqtlarda     izlangan     elementlarni     tez     izlab     topish
imkoniga  ega  bo’lamiz.
Boshida     q     ko’rsatkich     bo’sh,     p     esa     ro’yhat     boshini     ko’rsatadi;     p
ikkinchi     elementni     ko’rsatganda,     q     birinchini     ko’rsatadi.     Ro’yhat     boshi
ko’rsatkichi     (table)     birinchi     elementni     ko’rsatadi.     Ro’yhatda     key     kalitli
element     topilsa,     u     p     ko’rsatkich     bilan,     undan     oldingi     element     esa     q
ko’rsatkich     bilan     belgilanadi.     Shu     topilgan     p     elementni     ro’yhat     boshiga
joylashtiriladi.
Dastur  kodi:
node  *q=NULL;
node  *p=table;
8 while  (p  !=NULL){
if  (key  ==  p->k){
if  (q  ==  NULL)  {  //o‘rinlashtirish  shart  emas
search  =  p;
exit(0);
}
q=p;
p  =  p->nxt;
}
exit(0);
1.4 Indeksli ketma-ket qidiruv algoritmi.
Bu   qidirish   usulida   ikkita   jadval   tashkil   etiladi:   o’z   kalitlariga   ega   bo’lgan
ma’lumotlar   jadvali   (o’sish   tartibida   joylashtirilgan)   va   ma’lumotlar   kalitlaridan
tashkil   topgan   indekslar   jadvali.   Bu   yerda   birinchi   berilgan   argument   bo’yicha
indekslar   jadvalidan   ketma-ketlikda   qidirish   amalga   oshiriladi.   Kalitlarni   ko’rib
chiqishda   berilgan   kalitdan   kichigi   topilsa,   u   holda   ushbu   kichik   kalitni   asosiy
jadvaldagi   qidirishning   eng   quyi   chegarasiga   joylashtiramiz,   xuddi   shunday
berilgan   kalitdan   katta   deb   topilgan   kalitni   yuqori   chegaraga   joylashtiramiz.
Qidiruv   butun   jadval   bo’yicha   emas,   balki   quyi   chegaradan   yuqori   chegaragacha
amalga oshiriladi.
Ushbu qidiruv algoritmi quyidagicha (Psevdokodda):
i = 1
while (i <= m) and (kind(i) <= key) do
9 i=i+1
end while
if i = 1 then low = 1
else low = pind(i-1)
endif
if i = m+1 then hi = n
else hi = pind(i)-1
endif
for j=low to hi
if key = k(j) then
search=j
return;
endif
next j
search=0
return 0;
}
10 11 II. Qismiy ketma-ketlikni  qidirish  uchun  Knut  Morris   Pratt
algoritmi
2.1 Knut Morris Pratt algoritmi haqida
Knut-Morris-Pratt     algoritmi.   Matnda     namuna     satrni     izlovchi     ch е kli
avtomat  qurishda  boshlang`ich  holatdan  tugallovchi  holatga  o’tishlar  namuna
satrga     kiruvchi     simvollar     bilan     b е lgilab     olinadi.     Asosiy     muammo     namuna
satrga   tugallovchi   holatga   olib   k е lmaydigan   simvollarni   qo’shish   jarayonida
vujudga  k е ladi.
Knut-Morris-Pratt  algoritmi  ch е kli  avtomat  printsipiga  asoslanadi,  ammo
unda     mos     tushmaydigan     simvollarni     qayta     ishlashning     boshqaa     usulidan
foydalaniladi.     Ushbu     algoritmda     ch е kli     avtomat     holatlari     ayni     paytda     mos
tushishi  k е rak  bo’lgan  simvollar  orqali  b е lgilab  olinadi.  Har  bir  holatda  ikki
yo’nalishda   o’tish   imkoniyati   mavjud:   birinchisi   –   mos   tushish   ro’y   b е rgan
holat;   ikkinchisi   –   mos   tushish   ro’y   b е rmagan   holatga   to’g’ri   k е ladi.   Mos
tushish     ro’y     b е rganda     avtomatning     k е yingi     tugunga     o’tishi     yuzb е radi,     aks
holda   joriy   tugundan   oldingi   (orqaga)   tugunga   o’tish   yuz   b е radi.   Quyidagi
tasvirda   ababcb   namuna   satri   uchun   tuzilgan   Knut-Morris-Pratt   avtomatining
sx е matik  tuzilishi  ifoda  etilgan:
Har     bir     muvaffaqiyatli     o’tish     bajarilganda     Knut-Morris-Pratt   ch е kli
avtomatida  matndan  yangi  simvol  tanlanadi.  Muvaffaqiyatsiz  o’tishlarda  yangi
simvol  tanlanmasdan,  buning  o’rniga  oxirgi  marta  tanlangan  simvol  takroran
qayta     ishlanadi.     Agar     avtomat     tugallovchi     holatga     o’tsa,     matndan     namuna
satr  topildi  d е b,  hisoblanadi.  Quyida  ushbu  algoritm  matnini  k е ltiramiz:
subLoc=1//  Namuna  satrdagi  taqqoslanuvchi  joriy  simvol  ko’rsatkichi
textLoc=1//Matndagi  taqqoslanuvchi  joriy  simvol  ko’rsatkichi
while  textLoc<=length(text)  and  subLoc<=length(substring)  do
if  subLoc=0  or  text  [textLoc]=substring[subLoc]  then
textLoc=textLoc+1
subLoc=  subLoc+1
else  //  mos  tushmaslik  yuz  b е rdi;  mos  tushmaslik  bo’yicha  o’tish
subLoc=fail[subLoc]
12 end  while
if  (subLoc>length(substring)  then
return  textLoc-length(substring)+1//  topilgan  mos  tushish
else  return  0//  izlangan  namuna  topilmadi
end  if
Matn   ichida   qidiruv   uchun   brute-force   yondashuvining   kamchiligi   –
pattern’dagi belgilardan biri qidiruvda mos kelmay qolganda, qidiruvni boshqatdan
boshlashi   kerak.   Shuning   uchun   worst   case   O(N*M)   bo’lib   ketadi.   Misol   uchun,
bizda matn  A   B  A  A  A   A   B  A  A  A  A  A  A   A   A   A  bo’lsin. Pattern esa
BAAAAAAAAA .
Qidiruv jarayoni:
A  B  A  A  A  A  B  A  A  A  A  A  A  A  A  A
B    A  A  A  A  A  A  A  A  A
….B  A  A  A  A   A    A  A  A  A
…… B    A  A  A  A  A  A  A  A  A
…….. B    A  A  A  A  A  A  A  A  A
……… B    A  A  A  A  A  A  A  A  A
………… B    A  A  A  A  A  A  A  A  A
…………B  A  A  A  A  A  A  A  A  A
Mana ko`rib turibmizki, ikkinchi  siklda  patternning  6-belgisi  mos  kelmay
qoldi.     Demak     biz     text’dagi     biz     ko’rib     o’tgan     ohirgi     6     belgi     BAAAAB
ekanini  bilamiz.  Nima  uchun  qidiruvni  yana  boshqatdan  boshlashimiz  kerak?
3-6 sikllarni  tushirib  qoldirib,  7-sikldan  davom  ettirishning  imkoni  bormi?
13 Knuth-MorrisPratt     (KMP)     algoritmi     mana     shu     muammoga     yechim
sifatida     kelib,     qidiruvni     boshqatdan     boshlamaslikning     imkonini     beradi.     U
Deterministic  Finite  Automaton   g’oyasiga  asoslangan.
2.2 Patterndan DFA yasash:
Yuqoridagi  jadval  va  graph’ni  biz  o’zimi  ko’rib  turib  yasadik.  Kodda
qanday  qilib  berilgan  pattern’dan  DFAni  yasaymiz?
DFAni  yasashda  ikki  xil  holat  bor:
Mos   kelish .   j-holatida,   keyingi   belgi   c   ==   pattern.charAt(j)   bo’lsa,   u
holda  j  ni  bittaga  oshiramiz.
Mos  kelmaslik .   j-holatida,  keyingi  belgi  c   !=  pattern.charAt(j)   bo’lsa,
u  holda  ohirgi  j-1  belgilar  pattern[1..j-1]  ichida  bo’ladi.
1-Jadval:
function    dfaGenerator ( pattern )    {
     R    =    128
     const    M    =    pattern . length
     const    dfa    =    [ ... Array ( R ). fill ( null )]. map (()    =>    Array ( M ). fill ( 0 ))
dfa [ pattern . charCodeAt ( 0 )][ 0 ]    =    1
     for    ( let    x    =    0 ,    j    =    1 ;    j    <    M ;    j ++ )    {
         for    ( let    c    =    0 ;    c    <    R ;    c ++ )    {
             //  Copy  mismatched  cases
             dfa [ c ][ j ]    =    dfa [ c ][ x ]
             //  Set  match  case
             dfa [ pattern . charCodeAt ( j )][ j ]    =    j    +    1
14              //  Update  restart  state
             x    =    dfa [ pattern . charCodeAt ( j )][ x ]
         }
     }
     return    dfa
}
2.3 Knuth-Morris-Pratt  algoritmini  kodda  ifodalash
function    KMPSearch ( str ,    pattern )    {
     const    N    =    str . length
     const    M    =    pattern . length
     const    dfa    =    dfaGenerator ( pattern )
     let    i ,    j
     if    ( ! N    ||    ! M )    {
         return    -1
     }
     for    ( i    =    0 ,    j    =    0 ;    i    <    N    &&    j    <    M ;    i ++ )    {
         j    =    dfa [ str . charCodeAt ( i )][ j ]
     }
     if    ( j    ===    M )    {
         return    i    –    M
     }  
15         else    {
         return    N
     }
     function    dfaGenerator ( pattern )    {
         R    =    128
         const    M    =    pattern . length
         const    dfa    =    [ ... Array ( R ). fill ( null )]. map (()    =>    Array ( M ). fill ( 0 ))
         dfa [ pattern . charCodeAt ( 0 )][ 0 ]    =    1
         for    ( let    x    =    0 ,    j    =    1 ;    j    <    M ;    j ++ )    {
             for    ( let    c    =    0 ;    c    <    R ;    c ++ )    {
                 //  Copy  mismatched  cases
                 dfa [ c ][ j ]    =    dfa [ c ][ x ]
                 //  Set  match  case
                 dfa [ pattern . charCodeAt ( j )][ j ]    =    j    +    1
                 //  Update  restart  state
                 x    =    dfa [ pattern . charCodeAt ( j )][ x ]
             }
         }
         return    dfa
     }
}
16 /**
  *  USAGE
  */
Masofani     aniqlash     misolini     ko’rib     chiqaylik.     Shahar     viloyatlarini
birlashtiruvchi  avtomobil  yo’llari  tarmog’I  berilgan  bo’lsin.  Ba’zi  yo’llar  bir
tomonlama.  Shahar  markazidan  har  bir  viloyatga  eng  qisqa  yo’lni  topishimiz
zarur.
Keltirilgan     masalani     yechishda     Deykstraning     algoritmidan
foydalanishimiz   mumkin.   Algoritm   graflarga   asoslangan   bo’lib,   u   1959-   yil
niderlandiyalik     olim     E.     Deykstra     tomonidan     yaratilgan.     U     grafning     bitta
uchidan   boshqa   uchlarigacha   eng   qisqa   masofani   aniqlaydi,   bunda   grafning
yechimlari     manfiy    bo’lmasligi       lozim.    Bizdan     birinchi    uchdan    qolganlariga
borishning  qisqa  masofasini  topish  talab  qilinsin.
Doiralar     shaklida     uchlar,     chiziqlar     shaklida     ular     orasidagi     yo’l
tasvirlangan.  Doiralar  ichida  uchlarning  nomerlari,  elimentlari  ostida  ularning
ma’lumoti  –  yo’l  uzunligi  berilgan.  Har  bir  uchning  yonida  qizil  belgi  bilan
shu  uchga  birinchi  uchdan  eng  qisqa  masofa  uzunligi  belgilangan.
Tadbiq
1–uchning     belgisi     0     ga     teng     deb     hisoblanadi,     qolgan     uchlarning
belgilari    yetib   bo’lmas   darajada   juda   katta   sonlardan   iborat.   Bu   1–uchdan
boshqalarigacha     bo’lgan     masofa     hali     noma’lumligiki     ko’rsatadi.     Grafning
barcha  uchlari  ko’rilmagan  deb  belgilanadi.
                               Birinchi  qadam
Minimal     belgiga     1–uch     ega.     Uning     qo’shnilari     2,     3     va     6     uchlar.
Uchning     qo’shnilarini     navbat     bilan     ko’rib     chiqamiz.     1–uchning     birinchi
qo’shnisi     2–uch,     chunki     ungacha     bo’lgan     masofa     minimal.     1–uch     orqali
ungacha    bo’lgan    masofa    1–uchgacha     bo’lgan     qisqa    masofaning    summasiga
teng,     1–dan     2–ga     boruvchi     uning     belgisi     va     qovurg’asi     uzunligiga,     ya’ni
0+7=7.  Bu  2–uchning  joriy  belgisidan  (10000)  kichik,  shu  sababdan  ham  2–
uchning  yangi  belgisi  7  ga  teng.
Shunga   mos   ravishda   qolgan   qo’shnilar   (3   va   6   uchlar)   uchun   ham
yo’l   uzunligini   aniqlaymiz.   1-uchning   barcha   qo’shnilari   ko’rib   chiqildi.   1-
17 uchgacha     joriy     minimal     masofa     yakuniy     hisoblanadi     va     qayta     ko’rib
chiqilmaydi.  1-uch  ko’rib  chiqildi  deb  belgilanadi.
                            Ikkinchi  qadam
Birinchi   qadam   takrorlanadi.   Ko’rib   chiqilmagan   uchlardan   “yaqini”ni
topamiz.   Bu   2-uch   belgisi    7   ga   teng.   Yana   tanlangan   uchning   qo’shnilari
belgilarini  kamaytirishga  harakat  qilamiz,  bunda  ularga  2-uch  orqali  o’tamiz.
2-  uchning  qo’shnilari  1,  3  va  4  uchlar.
    1-uch     ko’rib    chiqilgan,    shu    sababdan    3-uch    ko’rib    chiqilmagan    va
uchlar  ichida  minimal  belgiga  ega.  Agar  unga  2  orqali  borilsa,  u  holda  bu
yo’lning     uzunligi     17     (7+10=17)     ga     teng     bo’ladi.     Ammo     3-uchning     joriy
belgisi  9  ga  teng,  ya’ni  9<17,  shu  sababdan  belgi  o’zgarishsiz  qoladi.
2-uchning  yana  bir  qo’shnisi  4-uch.  Agar  unga  2-uch  orqali  borsak,  u
holda     bunday     yo’lning     uzunligi     22     (7+15=22)     ga     teng.     22<10000     dan
bo’lganligi  sabab,  4-uchning  belgisini  22  ga  tenglaymiz.
2-uchning   barcha   qo’shnilari   ko’rib   chiqildi,   endi   uni   ko’rib   chiqilgan
sifatida  belgilaymiz.
Uchinchi     qadam.   3-uchni     tanlab     algoritmning     qadamini     takrorlaymiz.
Uni  “qayta  ishlab  chiqish”dan  so’ng  quyidagi  natijaga  ega  bo’lamiz.
To’rtinchi  qadam
Beshinchi  qadam
Oltinchi  qadam
Shu  tarzda  1-uchdan  5-uchga  eng  qisqa  masofa  1  –  3  –  6  –  5  uchlari
orqali  bo’ladi.  Shu  yo’l  orqali  biz  20  ga  teng  minimal  og’irlik  yig’amiz.
Minimal  masofa  haqida  xulosaga  keladigan  bo’lsak.  Har  bir  uch  uchun
yo’l   uzunligini   bilamiz   va   endi   uchlarni   oxirdan   ko’rib   chiqamiz.   Yakuniy
uchni     ko’rib     chiqamiz     (bu     holatda     5-uch).     U     bilan     bog’langan     barcha
uchlarni     ham     ko’rib     chiqamiz,     yakuniy     uch     yo’li     uzunligidan     mos
qovurg’aning   og’irligini   ayirgan   holda   yo’l   uzunligini   topamiz.   Bizda   5-uch
yo’l  uzunligi  20.  U  6  va  4  uchlar  bilan  bog’langan.  6-  uch  uchun  20-9=11
og’irlikka   ega   bo’lamiz   (mos   tushdi).   4-uch   uchun   20-6=14   og’irlikka   ega
bo’lamiz     (mos     tushmadi).     Agar     natijada     biz     ko’rilayotgan     uchning     (joriy
holda   6-uch)   yo’l   uzunligiga   mos   qiymatga   ega   bo’lsak,   u   holda   yakuniy
18 uchga     o’tish     aynan     o’sha     uchdan     amalga     oshirilgan     bo’ladi.     Bu     uchni
qidirilayotgan  yo’lda  belgilan  qo’yamiz.
6 -uchga  qaysi  qovurg’a  orqali  kelganimizni  aniqlaymiz.  Va  shu  holda
toki  boshiga  chiqmagunimizcha  davom  qildiramiz.
Agar     bunday     kuzatish     natijasida     bizda     qaysidir     qadamda     bir     nechta
uchlar   uchun   bu   qiymat   mos   tushsa,   u   holda   ulardan   ixtiyoriy   birini   olish
mumkin  –  bir  necha  yo’llar  bir  xil  uzunlikka  ega  bo’ladi.
Graf     –     bu     tugunlar     va     qirralar     (tugunlar     juftligini     birlashtiruvchi)
to’plamidan  iborat  bo’lgan  abstrakt  matematik  obyektdir.
4-Rasm:
Grafning elementlari  tarkibi  va  munosabatlar  tuzilishi  beriladi.  Grafning
tarkibiy  qismlari  bu  uning  tugunlari  va  qirralaridir.
5-Rasm:
Tarmoq
19 Bir   nechta   juft   tugunlararo   qirralardan   iborat    bo’lgan   turlicha   yo’llar
to’plami     mavjud     bo’lishi     mumkin.     Yopiq     yo’llar     –     sikllarning     mavjud
bo’lishi  tarmoqlarga  xos  xususiyatdir.
Yo’naltirilmagan  graf  yoki  simmetrik  bog’liqlik
Yo’naltirilmagan  graf  yoki  nosimmetrik  bog’liqlik
qirra  yoylar
Ilmoq  –  aynan  bitta  tugundan  chiqib,  yana  shu  tugunga  kiruvchi  qirra.
                                 III. Deykstra  algoritmi
Gollandiyalik     olim     Edsger     Deykstra     algoritmi     grafning     boshlang’ich
berilgan   tugunidan   boshlab   qolgan   barcha   tugunlargacha   bo'lgan   barcha   eng
qisqa     yo'llarni     topadi.     Uning     yordamida,     agar     barcha     zarur     ma'lumotlar
berilgan  bo'lsa,  masalan,  neft  va  shu  kabi  mahsulotlarni  eksport  qilish  uchun
bitta   shahardan   boshqa   shaharlarning   har   biriga   borish   uchun   qaysi    yo'llar
ketma-ketligini     tanlash     afzalroq     ekanligini     bilib     olish     mumkin.     Ushbu
usulning  salbiy  tomoni  shundaki,  manfiy  vaznga  ega  bo’lgan  qirralari  mavjud
bo'lgan   graflarni   qayta   ishlash   imkonining   mavjud   emasligi,   ya'ni,   masalan,
ba'zi    tizim    birorta   kompaniya   uchun   foydasiz   bo'lgan   marshrutlarni   taqdim
qilsa,    u    holda    u    bilan    ishlash    uchun     Dijkstraning     algoritmidan    foydalanib
bo’lmaydi.
Algoritmni     dasturiy     ta'minotini     amalga     oshirish     uchun     ikkita     massiv
kerak  bo'ladi:  mantiqiy  toifadagi   visited   -  tashrif  buyurilgan  tugunlar  haqidagi
20 ma'lumotlarni  saqlash  uchun  va  topilgan  eng  qisqa  yo'llar  kiritiladigan  butun
toifadagi    -     distance .    G={V,E}    graf    berilgan    bo’lsin.     V    to’plamga    tegishli
barcha    tugunlar    dastlab    tashrif     buyurilmagan   deb     belgilanadi,    ya’ni     visited
massivining     elementlariga     false     qiymat     berib     chiqiladi.     Eng     afzal     yo’lni
topish  masalasi  qaralyapti.    Distance    massivining  har  bir  elementiga  shunday
qilib  beriladiki,  ixtiyoriy  potensial  yo’ldan  katta  bo’lsin  (odatda,  bu  qiymatni
cheksiz     katta     qiymat     deb     qaraladi,     ammo     dasturda     berilgan     toifaning
qiymatlar  diapazonidagi  eng  katta  qiymat  sifatida  olinadi).  Boshlang'ich  nuqta
sifatida   s   tugun   tanlanadi    va   unga   nol   yo'l   belgilanadi:   distance   [s]   =   0,
chunki     s-dan     s-gacha     hech     qanday     qirra     yo'q     (bu     usulda     ilmoqlar
qaralmaydi).
Shundan     keyin,     barcha     qo'shni     tugunlar     topiladi     (s     dan     chiquvchi
qirralar   orqali)   [ularni    t   va   u   deb   belgilaylik]   va   ular   birma-bir    tekshirib
ko'riladi,     ya'ni     s     tugundan     har     bir     tugungacha     birma-bir     marshrut     bahosi
hisoblanadi:
-  distance[t]=distance[s]+  s  va  t  orasidagi  qirraning  vazni;
-  Distance[u]=distance[s]+  s  va  u  orasidagi  qirraning  vazni.
Ehtimoldan  xoli  emaski,  u  yoki  bu  tugunga  s  dan  bir  qancha  yo’llar
bo’lishi     mumkin.     Shu     sababli,     distance     massivida     bu     tugunga     bo’lgan
yo’lning     vaznini     qayta     ko’rib     chiqish     kerak     bo’ladi.     Shunda     kattaroq
(nooptimal)   qiymat   yo’qotiladi   va   tugunga   mos   yo’lning   vazniga   kichikroq
qiymat   beriladi.   s   tugun   bilan   qo’shni   bo’lgan   va   qarab   chiqilgan   tugunlar
tashrif  buyurilgan  sifatida  belgilab  chiqiladi,  yani  visited[s]=true  va  natijada,
s     dan     chiquvchi,     minimal     vaznga     ega     bo’lgan     yo’l     eltuvchi     tugun     faol
element  sifatida  belgilab  olinadi.  Faraz  qilamiz,  s  dan  u  gacha  masofa  t  ga
qaraganda   qisqa   bo’lsin.   Kelib   chiqadiki,   u   tugun   faollashadi   va   yuqoridagi
kabi  uning  qo’shnilari  (  s  dan  tashqari)  o’rganilib  chiqiladi.  u  tugun  tashrif
buyurilgan     deb     belgilanadi:     visited[u]=true,     endi     t     tugun     faollashadi     va
yuqoridagi     prosedura     uning     uchun     takrorlanadi.     Deykstra     algoritmi     s
tugundan  borish  mumkin  bo’lgan  barcha  tugunlar tadqiq qilinmaguncha davom
ettiriladi.
Algoritm  tarixi  uchta  mustaqil  matematiklar  bilan  bog'liq:  Lester  Ford,
Richard   Bellman   va   Edward   Moore.   Ford   va   Bellman   algoritmni   1956   va
1958  yillarda  nashr  etishdi,  Moore  esa  1957  yilda  taqdim  qilgan.  Va  ba'zan
uni     Bellman-Ford-Moore     algoritmi     deb     ham     atashadi.     Usul     ba'zi     vektorli-
marshrutlash    protokollarida,   masalan,    RIPda   (Routing    Information    Protocol)
qo'llaniladi.   Deykstra   algoritmi   singari,   Bellman-Ford   algoritmi   ham   vaznga
21 ega   bo’lgan   graflarda   bitta   tugundan   qolgan   barcha   tugunlarga   bo’lgan   eng
qisqa     masofani     aniqlashda     ishlatiladi.     Bu     algoritm     manfiy     elementga     ega
bo’lgan  graflar  bilan  ishlashda  ham  qo’llanilishi  mumkin
   
XULOSA
Xulosa   qilib   aytganda,   qidirish   o`zi   kompyuter   ma’lumotlarini   qayta
ishlashda   asosiy   amallardan   biri   hisoblanadi.   Uning   vazifasi   berilgan   argument
bo’yicha   massiv   ma’lumotlari   ichidan   maxsus   argumentga   mos   ma’lumotalarni
topish,   yoki   bunday   ma’lumot   yo’qligini   aniqlashdan   iborat.   Teng   bo’lish   orqali
qidiruv   o’sish   tartibida   tartiblangan   sonlar   massivi   berilgan   bo’lsin.   Bu   usulning
asosiy   g’oyasi   shundan   iboratki   tasodifiy   qandaydir   A
M   element   olinadi   va   bu   X
qidiruv agument bilan taqqoslanadi. Agar A
M =X bo’lsa qidiruv yakunlanadi. Agar
A
M   -> X bo’lsa, u holda indekslar m dan katta bo’lgan barcha elementlar kelgusi
qidiruvda chiqarib yuboriladi.
Asosan   bu   kurs   ishida   “Eng   katta   qismiy   ketma-ketikni   qidirish”   mavzusi
yoritildi.   Bunda   ikkilik   qidiruv,   intervalli   qidiruv,   chiziqli   qidiruvlarga   to’xtalib
o’tildi.   Hamda,   bu   mavzuni   asoslab   berishda   Knut   Morris   Pratt   va   Deykstra
algoritmaridan foydalanildi.
Kurs   ishi   kirish,   asosiy   qism,   xulosa   va   foydalanilgan   adabiyotlar
ro’yxatidan   iborat.   Asosiy   qism   uchta   bo’limni   o’z   ichiga   oladi.   Bular     qismiy
ketma-ketlikni   qidirish,   qismiy   ketma-ketlikni   qidirish   uchun   Knut   Morris   Pratt
agoritmi va Deykstra algoritmlari kabi bo’limlari haqida ko’plab qoidalar, misollar
hamda jadvallar ko’rib chiqildi.
Ushbu   kurs   ishida   “Eng   katta   qismiy   ketma-ketlikni   qidirish”   mavzusini
yozishda bir nechta adabiyotlar va internet manzillaridan foydalanildi.
 
22 23 FOYDALANILGAN ADABIYOTLAR
1. A.R.   Azamatov,   “Algoritimlash   va   dasturlash   asoslari”. Cho'lpon   nomidagi
nashriyot-matbaa ijodiy uyi Toshkent — 2013 .
2. B.B. Akbaraliyev. “Ma’lumotlar tuzilmasi va algoritimlar”. Toshkent – 2011.
3. B.   V.   SHabat.   Vvedenie   v   kompleksniy   analiz.   1-chast.   M.N.   1989. Nazarov
Fayzullo   Maxmadiyarovich,   “Algoritimlar   va   ma’lumotlar   strukturasi”.
Samarqand – 2019.
4. G. Xudayberganov, A. Vorisov, X. Mansurov. Kompleks analiz. Toshkent,
«Universitet», 1998.
5. G. Xudayberganov, A. Vorisov, X. Mansurov. Kompleks analiz. Karshi.
«Nasaf», 2003.
6. T.   X.   Holmatov,   N.   I.   Tayloqov .   Amaliy   matematika,   dasturlash   va
kompyuterning dasturiy ta`minoti. O quv qo llanmaʻ ʻ .  T :.  “Me h nat”, 2000 y. 
7. Virt N. Algoritm i strukturi dannix programmi .-M.:Mir, 1985.-405s  Sh. I. 
8. Razzoqov,   M.   J.   Yunusova.   Dasturlash:   Kasb-hunar   kollejlari   uchun   o quv	
ʻ
qo llanma. T. : “Ilm Ziyo”, 2011y. 	
ʻ
9. okhotin_algorithms_2019_l8.pdf (spbu.ru)   
10. Tez   katlama   algoritmini   qanday   qo'llash   kerak?   -   Astronomiya   -   2021   
(gsusigmanu.org)
11. Алгоритм Дейкстры нахождения кратчайшего пути (    prog    -   cpp    .   ru    )  
12. Алгоритм   Дейкстры.   Поиск   оптимальных   маршрутов   на   графе   /   Хабр   
(habr.com)
13. Это   маленькое   чудо   —   алгоритм   Кнута-Морриса-Пратта   (КМП)   /   Хабр   
(habr.com)
14. НОУ ИНТУИТ | Лекция | Алгоритмы поиска в тексте (intuit.ru)   
24

“Eng katta qismiy ketma-ketlikni qidirish” MUNDARIJA KIRISH. .......................................................................................................... 2 I Qismiy ketma-ketlikni qidirish ..................................................................... 3 1.1 Ketma-ket qidiruv algoritmi .................................................................. 3 1.2 Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi ......................... 5 1.3 Dastur kodi: ........................................................................................... 6 1.4 Indeksli ketma-ket qidiruv algoritmi. .................................................... 9 II. Qismiy ketma-ketlikni qidirish uchun Knut Morris Pratt algoritmi ......... 12 2.1 Knut Morris Pratt algoritmi haqida ..................................................... 12 2.2 Patterndan DFA yasash: ...................................................................... 14 2.3 Knuth-Morris-Pratt algoritmini kodda ifodalash ................................. 15 III. Deykstra algoritmi .................................................................................. 20 XULOSA ....................................................................................................... 22 FOYDALANILGAN ADABIYOTLAR ....................................................... 24

KIRISH. Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisobanadi. Algoritm ma’lum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi qoida hisoblanadi. “Qismiy ketma-ketlikni qidirish” asosan, algoritmda bu mavzuni yoritishimizda qidiruv nima ekanligiga to’xtalib o’tsak. Ma’lumotlarni qidirish algoritmlari bu- to’plam ma’lumotlar orasidan ma’lum bir kalit so’zga mos keluvchi elimentlarni qidirishga aytiladi. Ma’lumotlarni qidirish algoritmlari odatda ikki toifaga bo’linadi va bular quydagilar: Tarkibiy qidiruv: Bunda ro’yxat yoki qator ketma- ket o’tkaziladi va har bir eliment tekshiriladi. Bunga misol sifatida chiziqli qidiruvni keltirsak bo’ladi. Qidirish algoritmining eng soddasi bo’lgan chiziqli qidirish algoritmi, chiziqli ma’lumotlar tuzulmalaridan biror bir shart yoki qiymat bo’yicha eliment qidirishga mo’ljallangan va uning algoritmik murakkabligi quydagicha: Chiziqli qidirish algoritmining vaqt bo’yicha murakkabligi uning nomidan ham ma’lum, ya’ni chiziqli O(n). Ya’ni, eng yomon holat sifatida eliment array bo’lmagan holat qaraladi va bunda algoritm maximum n ta qadam ish bajarishi kerak bo’ladi. Intervalli qidirish- bu algoritmar maxsus ajratilgan ma’lumotlar tuzilmalarida qidirish uchun mo’ljallangan. Ushbu turdagi qidiruv algoritmlari Linear Search-ga qaraganda ancha samaralidir, chunki ular qayta-qayta qidiruv tuzulmasi markaziga yo’naladi va qidiruv maydonini ikkiga bo’ladi. Masalan: Ikkilik qidiruv. Ikkilik qidiruv- bu algoritmi asosan to’plamni ikkiga bo’lishlar orqali qidirishdan iborat. Ya’ni unda bo’linishlar toki kalit so’z topulmaganicha davom etadi. 2

I Qismiy ketma-ketlikni qidirish Kompyuterda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri hisoblanadi. Uning vazifasi berilgan argument bo’yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topish yoki bunday ma’lumot yo’qligini aniqlashdan iborat. Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yoki tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagona bo’lishi mumkin. Bunday noyob kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali ham qidiruvni amalga oshirish mumkin. Ma’lumotlar kalitini bir joyga yig’ish (boshqa jadvalga) yoki yozuv sifatida ifodalab bitta maydonga kalitlarni yozish mumkin. Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya’ni yozuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi. Kalitni berilgan argument bilan mosligini aniqlovchi algoritmga berilgan argument bo’yicha qidiruv deb ataladi. Qidiruv algoritmi vazifasi kerakli ma’lumotni jadvaldan topish yoki yo’qligini aniqlashdan iboratdir. Agar kerakli ma’lumot yo’q bo’lsa, u holda ikkita ishni amalga oshirish mumkin: 1. Ma’lumot yo’qligini indikatsiya qilish (belgilash) 2. Jadvalga ma’lumotni qo’yish. Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) – ma’lumot mavjud. Key – qidiruv argumenti. Unga rec - informatsion yozuv mos qo’yiladi. Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvning bir necha turlari mavjud. 1.1 Ketma-ket qidiruv algoritmi Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi. Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan element tartib raqamini saqlaydi). 3

Ketma-ket qidiruv algoritmi C++ tilida quyidagicha bo’ladi: int qidiruv(int key) { for (int i=0;i<n;i++)< p=""></n;i++)<> if (k[i]==key) { search = i;return search;} search = -1; return search; } } Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. M min = 1, M max = n. Agar ma’lumotlar massiv yacheykasida bir xil ehtimollik bilan taqsimlangan bo’lsa, u holda M o’rt  (n + 1)/2 bo’ladi. Agar kerakli element jadvalda yo’q bo’lib, uni jadvalga qo’shish lozim bo’lsa, u holda yuqorida keltirilgan algoritmdagi oxirgi ikkita operator quyidagicha almashtiriladi . n=n+1; k[n-1]:=key; r[n-1]:=rec; search:=n-1; return search; Agar ma’lumotlar jadvali bir bog’lamli ro’yhat ko’rinishida berilgan bo’lsa , u holda ketma-ket qidiruv ro’yhatda amalga oshiriladi. 1-Rasm Chiziqli bir bog’lamli ro’yhatdan key kalitga mos elementni ketma-ket qidiruv usuli yordamida izlab topish dasturi. Node *q=NULL; Node *p=lst; while (p !=NULL){ 4

if (p->k == key){ search = p; return search; } q = p; p = p->nxt; } Node *s=new Node;; s->k=key; s->r=rec; s->nxt= NULL; if (q == NULL){ s->nxt=lst; lst = s; } else q->nxt = s; search= s; return search; Ro’yhatli tuzilmaning afzalligi shundan iboratki, ro’yhatga elementni qo’shish yoki o’chirish tez amalga oshadi, bunda qo’shish yoki o’chirish element soniga bog’liq bo’lmaydi, massivda esa elementni qo’shish yoki o’chirish o’rta hisobda barcha elementlarning yarmini siljitishni talab qiladi. Ro’yhatda qidiruvning samaradorligi taxminan massivniki bilan bir xil bo’ladi. 1.2 Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi Faraz qilaylik, o’sish tartibida tartiblangan sonlar massivi berilgan bo’lsin. Ushbu usulning asosiy g’oyasi shundan iboratki, tasodifiy qandaydir A M element olinadi va u X qidiruv argumenti bilan taqqoslanadi. Agar A M =X bo’lsa, u holda qidiruv yakunlanadi; agar A M >X bo’lsa, u holda indekslari M dan katta bo’lgan barcha elementlar kelgusi qidiruvdan chiqarib yuboriladi. 5