O`zbekiston respublikasi axborot texnologiyalar va kommunikatsiyalarni rivojlantirish vazirligi muhammad

---

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALAR VA 
KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD 
AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR 
UNIVERSITETI Farg’ona filiali 
“
Algoritmlarni loyihalash
”
fanidan
Mustaqil ish 
Mavzu: Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. 
Variant №3 
Guruh: 650-21 
Bajardi: Azimova Ominaxon 

---

Mavzu: Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. 
Reja:
I.Kirish
1.Algoritm tushunchasi va uning ta’rifi.
II.Asosiy qism
2.Algoritmlarni baholash.
3. Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti.
III.Xulosa
IV.Foydalanilgan adabiyotlar. 

---

Kirish. 
Har qanday dasturchi uchun algoritmlar nazariyasining asoslarini bilish juda 
muhim, chunki algoritmlarning umumiy xususiyatlarini va ularni namoyish etish 
uchun rasmiy modellarni o'rganadigan fan. Hatto informatika darslaridan bizga 
kelajakda maktabga qaraganda murakkabroq topshiriqlarni yozishda yordam 
beradigan oqim jadvallarini tuzishga o'rgatiladi. Hech kimga sir emaski, deyarli har 
doim ma'lum bir muammoni hal qilishning bir necha yo'li mavjud: kimdir ko'p 
vaqt sarflashni, boshqalari resurslarni sarflashni o'z ichiga oladi, boshqalari esa 
deyarli echim topishga yordam beradi.
Siz har doim vazifaga muvofiq, xususan, muammolar sinfini hal qilish 
algoritmlarini ishlab chiqishda eng maqbul variantni izlashingiz kerak. 
Shuningdek, algoritm turli xil hajmlar va miqdorlarning boshlang'ich qiymatlarida 
o'zini qanday tutishi, unga qanday resurslar kerakligi va yakuniy natijani olish 
uchun qancha vaqt kerakligini baholash ham muhimdir.
Algoritm tushunchasi va uning ta’rifi.
Ma'lumotni qayta ishlash algoritmi - bu kompyuter fanida muammoni hal 
qilish usulining tavsifi bo'lib, uni keyinchalik tanlangan dasturlash muhitida 
amalga oshirish mumkin.
Algoritmni tahlil qilish - bu baholashni o'rganadigan informatika 
sohasidirishlash algoritmlari .
Algoritmning murakkabligi bu algoritmni tahlil qilishda hisobga olinadigan 
elementar operatsiyalar sonidir.
A algoritmi bilan belgilangan operatsiyalarning eng ko'p soni og'irlikning 
eng yomon holati bo'lib , u ma'lum bir o'lchovdagi D kirishlarni kiritadi .
Laboriousness eng yaxshi ishi algoritm operatsiyalar kichik soni A barcha 
yozuvlari da bir D ma'lum o'lchov n .
Laboriousness o'rtacha ishi algoritm operatsiyalar o'rtacha soni A barcha 
yozuvlari da bir D ma'lum o'lchov n . 
Algoritmning murakkabligi funktsiyasi - algoritmning murakkabligi bu D 
kirishidagi A parametr parametrlariga bog'liqligi .

---

Algoritmning vaqt murakkabligi eng yomon holatga algoritmning 
murakkablik funktsiyasini asimptotik baholashdir.
Xotira hajmi - D kirish uchun A algoritmini amalga oshirishda ishtirok 
etadigan xotira joylarining maksimal soni .
Algoritmning kapasitiv murakkabligi bu algoritmning eng yomon holatdagi 
xotira funktsiyasini asimptotik baholashdir. 
Algoritmning eng yomon, o'rta va eng yaxshi holatlaridagi resurslarning 
murakkabligi vaqt va funktsiyalar sinflarining tartiblangan juftligi.asemptomatik 
belgi bilan aniqlanadigan va ko'rib chiqilayotgan holatga mos keladigan sig'im 
murakkabligi .
Ma'lumotlar tuzilmalari bilan ishlash algoritmlari bu olinadigan asosiy 
tamoyillar va metodologiyani aniqlaydigan algoritmlardirma'lumotlarni qayta 
ishlash usullarini tushunish .
Saralash algoritmlari massivlar va fayllarni tartibga solish uchun 
mo'ljallangan algoritmlardir. 
Qidiruv algoritmlari bu katta ma'lumotlar to'plamida ma'lum elementlarni 
qidirish uchun mo'ljallangan algoritmlar.
Graf algoritmlari bu amalga oshirish uchun mo'ljallangan 
algoritmlardirgrafik ayirish va qidirish strategiyalari . 
Simlarni qayta ishlash algoritmlari bu belgilar ketma-ketligini qayta ishlash 
uchun bir qator usullarni o'z ichiga olgan algoritmlardir.
Geometrik algoritmlar bu geometrik ob'ektlardan foydalangan holda 
muammolarni echish uchun algoritmlardir. 
Algoritmni baholash 
Algoritmning murakkabligini o'lchashning bir necha usullari mavjud. 
Dasturchilar odatda algoritm tezligiga e'tibor qaratishadi, ammo boshqa 
ko'rsatkichlar ham bir xil ahamiyatga ega - xotira hajmiga, diskdagi bo'sh joyga 
talablar. Tez algoritmdan foydalanish, agar kompyuter ishlashi kerak bo'lganidan 
ko'proq xotirani talab qilsa, kutilgan natijalarga olib kelmaydi. 
Xotira yoki vaqt 

---

Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. 
Muammoni tezroq, katta hajmdagi xotiradan foydalangan holda yoki ozroq hajmni 
olib, sekinroq hal qilish mumkin. Bu holatda odatiy misol eng qisqa yo'llarni 
qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini taqdim etib, siz 
ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng qisqa masofani aniqlash 
uchun algoritm yozishingiz mumkin. Bu masofalarni kerak bo'lganda 
hisoblamaslik uchun barcha nuqtalar orasidagi eng qisqa masofani ko'rsatib, 
natijalarni jadvalga saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa 
masofani aniqlashimiz kerak bo'lsa, biz shunchaki jadvalning tugagan masofasini 
olishimiz mumkin. Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani 
talab qiladi. Katta shahar xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, 
yuqorida tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak. Bular 
Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb xotirani ishlatish 
kerak. Ushbu qaramlikdan kosmik-vaqt murakkabligi g'oyasi kelib chiqadi. Ushbu 
yondashuv bilan, algoritm bajarilish tezligi va iste'mol qilinadigan xotira nuqtai 
nazaridan baholanadi. Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo 
shunga qaramay, biz iste'mol qilingan xotiraning hajmini aniq belgilaymiz. 
Buyurtmani baholash 
Turli xil algoritmlarni taqqoslashda ularning murakkabligi kirish 
ma'lumotlari miqdoriga bog'liqligini bilish muhimdir. Masalan, bitta usul 
yordamida saralashda ming sonlarni qayta ishlash 1 s., Va million sonlarni qayta 
ishlash uchun 10 s vaqt kerak bo'ladi, boshqa algoritmdan foydalanish esa 2 s 
vaqtni talab qilishi mumkin. va 5 s. navbati bilan Bunday sharoitda qaysi algoritm 
yaxshiroq ekanligini aniq aytish mumkin emas. Umumiy holda, algoritmning 
murakkabligini kattalik tartibida baholash mumkin. Agar kirish ma'lumotlarining 
o'lchamlari oshgani sayin, algoritmning bajarilish vaqti f (N) funktsiyasi bilan bir 
xil tezlikda oshsa, algoritmda O (f (n)) murakkablik bor. A [NxN] matritsasi uchun 
har bir satrda maksimal elementni topadigan kodni ko'rib chiqing.
for i:=1 to N do
begin

---

max:=A[i,1];
for j:=1 to N do 
begin
if A[i,j]>max then
max:=A[i,j]
end;
writeln(max); 
end;
Ushbu algoritmda i o'zgaruvchisi 1 dan N.gacha o'zgaradi, i ning har bir 
o'zgarishi bilan birga, j o'zgaruvchisi ham 1 dan N ga o'zgaradi. Tashqi 
aylanishning har bir N takrorlanishida ichki pastadir ham N marta bajariladi. Ichki 
pastadir takrorlanishlarining umumiy soni N * N dir. Bu O (N ^ 2) algoritmining 
murakkabligini aniqlaydi. Algoritmning murakkablik tartibini taxmin qilishda 
faqat eng tez o'sadigan qismdan foydalanish kerak. Vazifalar aylanishi N ^ 3 + N 
ifodasi bilan tasvirlangan deb taxmin qiling. Bunday holda, uning murakkabligi O 
ga teng bo'ladi (N ^ 3). Funktsiyaning tez o'sib boruvchi qismini ko'rib chiqish, 
algoritmning xatti-harakatlarini N.ning ortishi bilan baholashga imkon beradi. 
Masalan, N = 100 bilan N ^ 3 + N = 1000100 va N = 1000000 o'rtasidagi farq atigi 
100 ga teng, bu 0,01%. O ni hisoblashda, ifodalarda doimiy omillarga e'tibor 
bermaslik mumkin. 3N ^ 3 ish bosqichiga ega bo'lgan algoritm O (N ^ 3) deb 
hisoblanadi. Bu O (N) nisbati muammoning hajmiga bog'liqligini yanada aniqroq 
qiladi. 
Qiyinchilikni aniqlash 
Dasturning eng murakkab qismlari odatda pastadir va qo'ng'iroq qilish 
protseduralari. Oldingi misolda butun algoritm ikki tsikl yordamida amalga 
oshirildi. Agar bitta protsedura boshqasini chaqirsa, u holda protseduraning 
murakkabligini batafsilroq baholash kerak. Agar unda muayyan miqdordagi 
ko'rsatmalar bajarilgan bo'lsa (masalan, bosib chiqarish), unda bu murakkablikni 
baholashga deyarli ta'sir qilmaydi. Agar O (N) bosqichlar chaqirilayotgan 
protsedurada bajarilsa, funktsiya algoritmni sezilarli darajada murakkablashtirishi 

---

mumkin. Agar protsedura ko'chadan ichkarisiga chaqirilsa, u holda ta'sir yanada 
katta bo'lishi mumkin. Misol tariqasida ikkita protsedurani ko'rib chiqing: O (N ^ 
3) murakkabligi bilan sekin va O (N ^ 2) murakkabligi bilan. 
procedure Slow;
var i,j,k: integer;
begin
for i:=1 to N do 
for j:=1 to N do
for k:=1 to N do
какое-то действие}
end;
procedure Fast; 
var
i,j: integer;
begin
for i:=1 to N do 
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end; 
Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchun 
zarur bo'lgan vaqt va talab qilinadigan xotira miqdori hisoblanadi. Shuningdek, 
topshiriqlar sinfi uchun murakkablikni tahlil qilganda ma'lum bir ma'lumotni - 
kirish hajmini tavsiflovchi ma'lum bir raqam aniqlanadi . Shunday qilib, 
algoritmning murakkabligi kirish hajmining funktsiyasi degan xulosaga kelishimiz 
mumkin. 

---

Algoritmning murakkabligi bir xil kirish hajmi bilan farq qilishi mumkin, 
ammo har xil kirish ma'lumotlari. Eng yomon , o'rta yoki eng yaxshi holatda 
murakkablik tushunchalari mavjud . Odatda, eng yomon ishning murakkabligi 
baholanadi. Vaqtning murakkabligi eng yomon holatda, berilgan o'lchamdagi 
masalani echishda algoritmni bajarish paytida bajariladigan operatsiyalarning 
maksimal soniga teng bo'lgan kirish hajmining funktsiyasi. Eng yomon holatda, 
kapasitiv murakkablik bu o'lchamdagi muammolarni echishda foydalanilgan xotira 
hujayralarining maksimal soniga teng kirish hajmi funktsiyasidir. 
Algoritmni o'sish tartibi 
Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik) katta kirish 
o'lchamiga ega bo'lgan algoritmning murakkablik funktsiyasining taxminiy xatti-
harakatlarini tavsiflaydi. Bundan kelib chiqadiki, vaqtning murakkabligini 
baholashda elementar operatsiyalarni ko'rib chiqishga hojat yo'q, algoritmning 
bosqichlarini ko'rib chiqish kifoya qiladi. 
Algoritmning bosqichi bu ketma-ket joylashgan elementar operatsiyalar 
to'plami bo'lib, ularning bajarilish vaqti kirish hajmiga bog'liq emas, ya'ni u 
yuqorida qandaydir doimiy bilan chegaralangan. 
Asimptotik baholash turlar 
O - eng yomon holat 
F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchamini 
n> 0 ko'rib chiqing . Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , 
n 0 > 0 , keyin 0 n 0 . 
Bu holda g (n) funktsiya f (n) ning asemptomatik ravishda aniq qiymatidir. 
Agar f (n) algoritmning murakkabligi funktsiyasi bo'lsa, unda murakkablik tartibi f 
(n) - O (g (n)) deb belgilanadi. 
Bu ibora g (n) dan doimiy omilgacha tez o'smaydigan funktsiyalar sinfini 
belgilaydi. 
Θ - o'rtacha ish uchun ball 

---

Ta'kidlash joizki, n> n 0 uchun f (n) funktsiya hamma joyda c 1 * g (n) va c 
2 * g (n) orasida bo'ladi , bu erda c doimiy omil. Masalan, f (n) = n 2 + n bilan ; g 
(n) = n 2 .