10-Amaliy ish Graflar bilan ishlovchi soda algoritmlar

for all 256 simvol do 
hisobchiga nol qiymatni o‘zlashtirish 
end for 
while faylda tekshirilmagan simvollar bor do 
keyingi simvolni kiritish 
o‘qilgan simvol soni hisobchisini bittaga oshirish 
end while 
Algoritm ishini ko„rib o„taylik: bunda u initsializatsiya siklida 256 ta o„tishni amalga 
oshiradi. Agar faylda N ta simvol bo„lsa, for siklida sikl o„zgaruvchisi initsializatsiya qilinib, 
so„ngra o„zgaruvchining sikl doirasidan chiqmaganligi tekshiriladi va qiymati bittaga oshiriladi. 
Bundan initsializatsiya siklida 257 ta (bitta sikl o„zgaruvchisi uchun, 256 ta sikl 
o„zgaruvchisining orttirilishi uchun) o„zlashtirish hamda 257 ta (o„zgaruvchining sikl doirasidan 
chiqib ketmaganligini tekshirish va bitta siklni to„xtatish uchun) tekshirish amali bajarilishi kelib 
chiqadi. Ikkinchi siklda N + 1 (+1 fayl bo„shagandan keyingi oxirgi tekshirish) marta shart 
tekshirish va hisobchini N marta o„stirish bajariladi. Hamamsi bo„lib amallar soni quyidagicha:
o„stirishlar soni N+256 ta ; o„zlashtirishlar soni 257 ta; shartlarni tekshirishlar soni N + 258 ga 
teng. Shunday qilib, 500 simvollik faylni qayta ishlovchi algoritm 1771 ta amal bajaradi. Bundan 
770 (43%) tasi initializatsiyaga tegishli. Agar fayl 50 000 ta simvolni o„zida saqlasa, algoritm 
100 771 amalni bajarib, bulardan 770(1% dan kamroq) initsializatsiyaga tegishli bo„ladi. 
Initsializatsiya jarayoni algoritmning vaqt bo„yicha ko„rsatkichlariga aytarli ta‟sir ko„rsatmaydi.
Boshlang„ich berilganlar sinflari

---

Algoritmlar tahlili jarayonida boshlang„ich kirish ma‟lumotlarining ahamiyati kattadir. Chunki 
algoritmning bajarilish ketma-ketligi to„g„ridan-to„g„ri boshlang„ich berilganlarga bog„liq 
bo„ladi.Masalan, N ta elementdan iborat ro„yxatdan eng kattasini topish uchun quyidagi 
algoritmldan foydalanish mukin:
largest = list [1] 
fori=2 toN do 
if (list [i] > largest) then 
largest = list [i] 
end if 
end for 
Agar berilgan ro„yxat kamayib borish tartibida saralangan bo„lsa, sikl oldidan bitta 
o„zlashtirish amali bajarilib, sikl tanasida o„zlashtirishlar bajarilmaydi.Agar ro„yxat o„sib borish 
tartibida saralangan bo„lsa, hammasi bo„lib, N ta o„zlashtirish (bitta sikl oldidan va N -1ta sikl 
ichida) amali bajariladi. Tahlil jarayonida boshlang„ich berilganlarning turli mukin bo„lgan 
to„plamlari ko„rib o„tiladi. Bunda berilganlar to„plamlari sinflarga bo„linib o„rganiladi. Masalan, 
10 ta sondan iborat ro„yxatdagi joylashtirishlar soni 3 628 800 ga teng.Ushbu sonli ro„yxatga 
eng katta elementni izlash algoritmini qo„llayiz. Bunda boshlang„ich berilganlarning birinchi 
elementi eng katta bo„lganlarining soni 362 880 ga teng.Ularning barchasini bir sinfga 
birlashtirish mumkin.Eng katta element ikkinchi o„rinda turgan to„plamlar soni ham 362 880 ta. 
Ularni boshqa sinfga birlashtirish mumkin. Bunda algoritmning bajarilish jarayonida amalga 
oshiriladigan o„zlashtirish amallarining soni eng katta elementning ro„yxatda egallagan tartib 
raqamiga teng bo„ladi. Shunday qilib, barcha boshlang„ich berilganlar to„plamlarini bajariladigan 
o„zlashtirish amallari soniga qarab N ta turli sinfga ajratish mumkin.
Algoritmlar tahlilida boshlang„ich ma‟lumotlarni tanlash uning bajarilishiga sezilarli ta‟sir 
ko„rsatadi.Jumladan, saralash algoritmlari boshlang„ich ketma-ketlik saralangan bo„lsa, juda tez 
ishlagani holda, boshqa algoritmlar xuddi shu boshlang„ich berilganlar ustida ishlashning 
o„rtacha natijasini ko„rsatadi. Shuning uchun algoritmlarning bitta boshlang„ich berilganlar 
to„plami bilan ishlashini tahlil qilish emas, algoritmning eng tez ishini hamda yeng sekin ishini 
ta‟minlovchi boshlang„ich berilganlar to„plamlarini izlash maqsad qilib qo„yiladi. Bundan 
tashqari tekshiriluvchi algoritmning barcha mumkin bo„lgan boshlang„ich berilganlar 
to„plalarida ko„rsatadigan natijalarining o„rtacha qiymatlari ham baholanadi. 
Eng yaxshi holat Boshlang„ich berilganlarning algoritm bajarilishining minimal vaqtini 
ta‟minlovchi to„plami eng yaxshi holatni bildiradi. Ushbu boshlang„ich berilganlar bilan 
ishlaganda algoritm eng kam sondagi amallarni bajaradi.Agar masalan, izlash algoritmi 
tekshirilayotgan bo„lsa, berilganlar to„plami eng yaxshi hisoblanadi, qachonki izlanayotgan 
obyekt tekshiriluvchi yacheykalarning eng birinchisida joylashtirilgan bo„lsa 
Eng yomon holat
Algorit ishining eng yomon holatini tahlil etish ham juda muhim ahamiyatga ega. Chunki bu 
algoritm ishining umkin bo„lgan maksimal vaqtini aniqlash imkonini beradi. Eng yomon holatni 
tahlil qilishda algoritm eng ko„p ish bajaruvchi boshlang„ich berilganlar to„plami izlanadi. Izlash 
algoritmi uchun bunday berilganlar to„plami – bu izlangan element teshiriluvchi obyektlardan 
eng oxirgisi bo„lgan yoki butunlay mavjud bo„lmagan ro„yxatdir. Eng yomon holat tahlili 
algoritm ishlash vaqtining yuqori bahosini beradi.
O„rtacha holat 
O„rtacha holat tahlili yeng murakkab bo„lib hisoblanadi, chunki bunda bir necha etapdan iborat 
ish bajariladi. Birinchi qadamda mumkin bo„lgan boshlang„ich berilganlar guruxlari sinflarga 
ajratiladi.Ikkinchi qadamda har bir berilganlar to„plamining sinflarga tegishli bo„lish ehtimoli 
aniqlanadi. Keyingi qadamda xar bir sinfga tegishli berilganlar sinfi bilan ishlashda algoritmning 
sarf qiladigan vaqti hisoblanadi. Ushbu vaqt bir sinfga tegishli berilganlar to„plamlari uchun bir 
xil bo„lishi kerak. O„rtacha vaqt quyidagi formula bilan aniqlanadi: 

---

 ( ) ∑
( )
Bu yerda n - boshlang„ich berilganlar xajmi, m – sinflar soni pi - berilganlar 
to„plamining i nomerli sinfga tegishli bo„lish ehtimoli, ti - algoritmning i- sinfga tegishli 
berilganlarni qayta ishlashga sarflaydigan vaqti. 
Ba‟zi holatlarda berilganlar to„plamlarining sinflarga tegishli bo„lish ehtimoli bir-biriga 
teng bo„ladi. Boshqacha aytganda, agar sinflar soni beshta bo„lsa, har bir sinfga tegishli bo„lish 
ehtimoli 0,2 ga teng. Bunday holda algoritm ishining o„rtacha vaqtini yuqoridagi forula bilan 
hisoblash yoki unga ekvivalent soddalashtirilgan formula bilan hisoblash mukin: 
( )
∑
( )
 
Xotira bo„yicha murakkablik 
Algoritmlar asosan sarf etadigan vaqti bo„yicha qiyoslansa ham,u yoki bu algoritmning 
ishlashi uchun egallaydigan xotira xaji ham e‟tiborga molikdir. Kompyuterlar rivojining 
boshlang„ich davrlarida xotira resurslarining yetishovchiligi sharoitida algoritmlarning 
xotiratalablik bo„yicha tahlili prinsipial ahamiyatga ega edi. Ko„pgina holatlarda dasturchilar 
sekinroq ishlaydigan, ammo qo„shimcha xotira talab qilmaydigan algoritmlarni tanlashga majbur 
bo„lganlar.Xotira resurslariga talab juda katta bo„lganligidan qaysi ma‟lumotlar saqlanishi kerak, 
saqlashning effektiv usullari?,- degan savol ham dolzarb hisoblangan. Hozirgi vaqtda ishlab 
chiqarilayotgan dasturiy ta‟minotga qarab , xotira resurslarini iqtisod qilish usullariga yeralicha 
e‟tibor berilmayotganligining guvohi bo„lamiz. Xatto juda sodda dasturlarning ishi uchun zarur 
bo„lgan xotira xajmi megabaytlarda o„lchanadi. Dasturiy ta‟minot ishlab chiqaruvchilarini
xotirani iqtisod qilish muammosi endilikda qiziqtirmayotir. 
O„sish tezligi
Algoritmlar tahlilida algoritm bajaradigan amallarning soni ahamiyatga ega bo„lmasdan, 
ularning boshlang„ich berilganlar soni ortgandagi o„sish tezligi tekshiriladi. Ushbu kattalik 
algoritmning o„sish tezligi deb ataladi. 
Funksiyalar o„sish tezliklari grafiklari 
O„sish tezliklari tasvirida to„rtta funksiyaning grafiklari keltirilgan. x2 funksiya oldin sekin 
o„sadi, ammo x ning o„sib borishi bilan uning o„sish tezligi ham ortib boradi; x+10 va 3x-2 
funksiyalarning o„sish tezligi o„zgarmasdan qoladi; 2 log x funksiya butunlay o„smayotgandek 
ko„rinsada, u juda sekin tezlik bilan o„sadi. 

---

Funksiyalar o„sish tezliklari jadvali 
2-rasmda ba‟zi tez-tez uchrab turuvchi funksiyalarning o„sish tezligi o„z ifodasini topgan. 
Rasmdan funksiyalarning qiymatlari kichik argumet naborlari uchun bir biridan kam farq 
qilsada, ushbu naborlar xajmining o„sishi bilan bu farqlar ham o„sib boradi. 1- va 2-rasmlardagi 
ma‟lumotlar funksiyalarning yana bir xususiyatini ifodalaydi. Bu xususiyatga ko„ra algoritmning 
o„sish tezligini hisoblashda tez o„suvchan funksiyalar olinib, sekin o„suvchan funksiyalar 
tashlab yuboriladi . Masalan, algoritmning o„sish tezligi x3-30x ifoda bilan hisoblansa, x3 ning 
o„zi hisoblanadi, chunki 100 ta boshlang„ich berilganlar uchun x3-30x bilan x3 orasidagi farq 
3%ni tashkil qiladi. 
O„sish tezligi klassifikatsiyasi 
Algoritmlarni ular murakkabligining o„sish tezligi bo„yicha sinflashtirish mukin. Bunda 
klassifikatsiya uchta kategoriya bo„yicha amalga oshiriladi:a) murakkablik tezligi (tartibi yoki 
o„sish funksiyasidagi tez o„suvchan qism funksiya) o„rtacha tezlik funksiyasi o„sish tezligi kabi 
o„sib boruvchi algoritmlar; b) murakkablik tezligi o„rtacha tezlik funksiyasi bilan bir xil 
tezlikda o„sib boruvchi algoritmlar; murakkablik tezligi o„rtacha tezlik funksiyasi o„sish 
tezligidan sekin o„suvchi algoritmlar. 
Katta omega Birinchi kategoriyaga taalluqli funksiyalar sinfi Ω(f) bilan belgilanadi. D funksiya 
ushbu Ω sinfga taalluqli bo„ladi, qachonki n argumentning qandaydir oldindan belgilangan s 
(musbat son) dan katta barcha qiymatlari uchun d(n)>cf(n) shart o„rinli bo„lsa. 
Katta O
Uchinchi kategoriyaga taalluqli funksiyalar sinfi O(f) bilan belgilanadi. Ushbu sinf o„rtacha 
qiymat tezligidan sekin o„sadigan funksiyalardan iborat. D funksiya ushbu sinfga taalluqli 
bo„ladi, qachonki n argumentning qandaydir oldindan belgilangan s (musbat son) dan katta 
barcha qiymatlari uchun d(n) Katta teta 
Θ(f) bilan murakkablik tezligi o„rtacha tezlik funksiyasi bilan bir xil tezlikda o„sib boruvchi 
funksiyalar sinfini belgilayiz. Formal nuqtai nazardan qaraganda ushbu sinf yuqorida keltirilgan 
ikki sinfning kesishmasidan iboratdirdir: Θ(f)= Ω(f)∩ O(f). 
Dasturlar tahlili 
Faraz qilaylik, bizga katta va murakkab dastur berilgan bo„lsin. Ushbu dasturni tezroq ishlashini 
qanday ta‟minlash mumkin? Dasturning qayta ishlanishi(modifikatsiyalanishi) mumkin bo„lgan 
qismlarini qanday aniqlash mumkin? Buning uchun dasturdagi hisoblashlar va sikllar ko„p 
bo„lgan qismdasturlarni aniqlab, ularni takomillashtirish mumkin bo„ladi. Ammo oldiniga dastur 
ishida eng ko„p qatnashuvchi qismdasturlarni aniqlab olish kerak bo„ladi. Buning usullaridan biri 
har bir qismdasturga global hisobchi qo„yishdan iborat. Ushbu hisobchi-o„zgaruvchilarning 
boshlang„ich qiymati 0 ga tenglashtirilib, so„ngra qismdasturga har bitta murojaat vaqtida 
qiymati bittaga oshirib boriladi. Dastur ishini tugatgach, hisobchilarning qiymatiga qarab, qaysi 
qism dastur necha marta ishlagani ma‟lum bo„ladi. 

---

O„rniga qo„yish bilan saralash algoritmi 
Ushbu saralash algoritmining asosiy mohiyati saralangan ro„yxatga yangi element qo„shishda
uni “o„z joyiga” joylashtirishdan iboratdir. Bunda algoritm saralanuvchi ro„yxat birinchi 
elementini uzunligi 1 ga teng bo„lgan saralangan ro„yxat deb qabul qilib, ikkinchi elementni 
yangi yaratilayotgan saralangan ro„yxatning “kerakli” joyiga joylashtiradi. So„ngra berilgan 
ro„yxatning uchinchi elementi ham saralangan ikki elementli ro„yxatdagi o„z joyiga 
joylashtiriladi va hokazo. Ushbu jarayon berilgan ro„yxatning barcha elementlari saralangan 
ro„yxatga joylashtirib chiqilgunga qadar davom ettiriladi. O„rniga qo„yish algoritmining ifodasi 
quyidagidan iborat: 
InsertSort(List,N) 
List elementlarning saralanuvchi ro„yxati 
N ro„yxatdagi elementlar soni 
For i=2 to N do 
newElement=list[i] 
location=i-1 
while (location) >=1) and(list[location]> newElement) do 
{navbatdvgi elementdan kattalarini surish} 
list[location+1]= list[location] 
location= location-1 
end while 
list[location+1]= newElement 
end For 
Ushbu algoritm newElement o„zgaruvchisiga yangi o„rniga qo„yiluvchi qiymatni kiritadi. 
So„ngra bu yangi elementga joy ajratish uchun massiv elementlari bir pozitsiyaga suriladi (while 
sikli). Siklning oxirgi iteratsiyasi location+1 nomerli elementni location+2 pozitsiyaga 
o„tkazadi,ya‟ni location+1 pozitsiyasi yangi element uchun bo„shatiladi. 
Eng yomon holat tahlili
while siklida amallar eng ko„p bajariladi, qachonki ro„yxatning saralangan qismiga yangi 
qo„shiluvchi element bu ro„yxat elementlarining barchasidan kichik bo„lsa. Bu holatda sikl 
location o„zgaruvchisining qiymati 0 ga teng bo„lganda to„xtaydi.Shuning uchun har bir yangi 
element ro„yxatning boshidan joy olsa, algoritm eng ko„p ish bajaradi. Bu faqat berilgan ro„yxat 
elementlari kamayib borish tartibida joylashgan bo„lgandagina mumkindir.Bu holat eng yomon 
holatlardan biridir.Bunday ro„yxatni qayta ishlash jarayoni quyidagicha aalga oshiriladi: birinchi 
bo„lib berilgan ro„yxatning ikkinchi elementi joylashtiriladi.U faqat bitta element bilan 
taqqoslanadi. Ikkinchi joylashtiriluvchi element oldingi ikkitasi bilan taqqoslanadi, uchinchisi 
esa oldingi uchtasi bilan va hokazo i – element oldingi i ta element bilan taqqoslanadi. Shunday 
qilib, jarayon N - 1 marta takrorlanadi. O„rniga qo„yishlar bilan saralash algoritmining 
murakkabligi eng yomon holat uchun quyidagicha hisoblanadi: 
( ) ∑
( ) 
( ) ( 
)
O„rtacha holat tahlili
Ushbu tahlil jarayonini ikki etapga ajratamiz. Oldiniga navbatdagi elementning pozitsiyasini 
aniqlash uchun zarur bo„lgan taqqoslashlar o„rtacha sonini hisoblaymiz. So„ngra ushbu 
miqdordan foydalanib barcha amallarning o„rtacha qiymatini hisoblash mumkin.Bitta element 
uchun mumkin bo„lgan pozitsiyalar nechtagacha bo„ladi? 
Saralangan ro„yxatga qo„shiluvchi birinchi element uchun ikkita umkin bo„lgan holat mavjud: u 
ikki elementli ro„yxatda birinchi yoki ikkinchi pozitsiyani egallaydi. Ikkinchi elementda uchta 
mumkin bo„lgan holat bo„ladi:birinchi, ikkinchi yoki uchinchi. Demak, i-element mumkin 
bo„lgan i + 1 ta pozitsiyadan birini egallaydi. Faraz qilaylik, bu imkoniyatlarning ehtimoli o„zaro 

---

teng bo„lsin. U holda i-elementni saralangan ro„yxatga qo„shish uchun bajariladigan barcha 
amallarning o„rtacha qiymati quyigi formular bilan hisoblanadi:
(∑
) (
( )
)
 
Biz i-elementni saralangan ro„yxatga qo„shish uchun bajariladigan amallarning o„rtacha 
qiymatini hisobladik. Endi ushbu natijani berilgan ro„yxatning N-1 ta elementlari uchun yig„ib 
chiqamiz: 
( ) ∑
∑ (
)
( ) ( 
)
 
 
Pufakchali saralash
Pufakchali saralash algoritmining mohiyati kichik qiymatlarning ro„yxat yuqorisiga itarilib, yirik 
qiymatlarning ro„yxat pastiga surilishiga asoslangan. Pufakchali saralashning ko„p variantlari 
mavjud bo„lib, ulardan birini ko„rib o„tamiz. Bunda algoritm ro„yxat bo„ylab bir necha o„tishni 
bajaradi. Har bir o„tishda qo„shni elementlar bir-biri bilan taqqoslanadi.Agar bu elementlarni 
tartibi noto„g„ri bo„lsa, ularning o„rinlari almashtiriladi.Har bir o„tish ro„yxat boshidan 
boshlanadi. Oldin birinchi va ikkinchi element taqqoslanadi, keyin ikkinchi va uchinchisi va 
hokazo. Bunda ro„yxatning eng katta elementi birinchi o„tish tugagandan keyin ro„yxatning 
oxiridan joy oladi.Ikkinchi o„tishda kattalik bo„yicha ikkinchi element ixiridan ikkinchi o„rinni 
egallaydi. Agar biror o„tishda bitta ham o„rin almashtirish bajarilmasa, bro„yxat saralangan deb 
hisoblanib, algorit ishi to„xtatiladi. Quyida pufakchali saralash algoritmining ifodasi keltirilgan: 
BubbleSort(list,N) 
List Elementlarning saralanuvchi ro„yxati 
N Ro„yxatdagi elementlar soni 
Namber=N 
swappedElamaents=true 
while swappedElamaents do 
Namber= Namber-1 
swappedElamaents=false 
For i=1 to Namber do 
If list[i]> list[i+1] then 
Swap(list[i], list[i+1]) 
swappedElamaents=true 
end if 
end for 
end while 
Eng yaxshi holat tahlili
Algoritm bajaradigan ishning xajmi minimal bo„lgan holatni ko„rib o„tamiz. Birinchi o„tishda 
sikl to„liq bajarilganligi uchun algoritmda eng kamida N – 1 taqqoslash bajariladi.Bunda ikki 
imkoniyat ko„rib chiqilishi kerak: birinchi o„tishda hech bo„lmasa bitta almashtirish bo„lgan; 
almashtirish bo„lmagan. Birinchi holatda swappedElements o„zgaruvchisining qiymati rost, 
demak N - 2 ta taqqoslashni talab qiluvchi while sikli takror bajariladi. Ikkinchi holatda 
swappedElements o„zgaruvchisining qiymati yolg„on, demak algoritm bajarilishi 
to„xtaydi.Shuning uchun eng yaxshi holatda N – 1 ta taqqoslashlar bajarilib, birinchi o„tishda 
o„rin almashtirishlar bo„lmaydi. Bundan eng yaxshi berilganlar to„plami talab qilingan tartibda 
joylashgan elementlar ro„yxatidan iborat ekanligi bildiradi. 
Eng yomon holat tahlili
Eng yaxshi holatda berilganlar to„plami talab qilingan tartibda joylashgan elementlardan iborat 
bo„lsa, eng yomon holatda berilganlar teskari tarbida joylashgan elementlardan iborat bo„lishi 

---

mumkinmi? Agar eng katta element ro„yxatda birinchi turgan bo„lsa, u barcha qolgan elementlar 
bilan o„rin almashtirib chiqishi kerak. Birinchi o„tish boshida kattalik bo„yicha ikkinchi element 
ikkinchi o„rinni egallab turadi, ammo birinchi taqqoslash va o„rin almashtirishdan natijasida u 
birinchi o„ringa o„tkaziladi. Ikkinchi o„tish boshida ro„yxat boshida kattaliu bo„yicha ikkinchi 
elemment turadi va u qolgan barcha elementlar bilan o„rin almashadi.Bu jarayon barcha qolgan 
elementlar uchun takrorlanganligi uchun For sikli N - 1 marta bajariladi. Shunday qilib, eng 
yomon holatda nechta taqqoslash bajariladi? Birinchi o„tishda qo„shni qiymatlarni N – 1 
taqqoslash bajariladi, ikkinchi o„tishda N - 2 ta. Har bir keyingi o„tishda taqqoslashlar soni 1 ga 
kamayadi. Shuning uchun eng yomon holat uchun murakkablik quyidagi forula bilan 
hisoblanadi: 
( ) ∑ ∑
( ) 
( 
)