Mustaqil ish mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari. Bajardi: Pardayev Jonibek Tekshirdi: Narmanov Otabek

Algoritm tushunchasi va uning ta’rifi.
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 kelajakd
a
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.
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 mi
sol eng qisqa
yo'llarni qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini
taqdim etib, siz ushbu tarmoqning har qanday ikkita nuqtasi orasidagi en
g qisqa
masofani aniqlash uchun algoritm yozishingiz mumkin. Bu masofalarni k
erak 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, bizshunchaki jadvalning tugagan masofasini olishimiz mum
kin. 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
jadvalda10 milliarddan ortiq hujayralar bo'lishi kerak. Bular Algoritmnin
g
ishlashini
yaxshilash
uchun
qo'shimcha
10 Gb xotirani ishlatish kerak. Ushbu qaramlikdan kosmik-vaqt murakka
bligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan, algoritm bajarilihtezli
gi
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 a
niq aytish mumkin emas.
Umumiy holda, algoritmning murakkabligini kattalik tartibida baholash
mumkin. Agar kirish ma'lumotlarining o'lchamlari oshgani sayin, algorit
mning 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]
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'sadiga
n qismda
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 chiqi
sh, 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's
ir
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.
Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchu
n 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 de
gan 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 murakk
abligi
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.

---