Zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish



Download 432,32 Kb.
Pdf ko'rish
bet1/3
Sana01.06.2022
Hajmi432,32 Kb.
#628367
  1   2   3
Bog'liq
1-mustaqil ishi



O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA 
KOMMUNIKATSIYALARINI RIVOJLANTIRISH 
VAZIRLIGI 
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT 
TEXNOLOGIYALARI UNIVERSITETI 
QARSHI FILIALI
 
 
TT-11-19 – guruh talabasi Ibodillayev Orifjonning 
 

 
Agoritm murakkabligini static va dinamik o’lchovlari.
 
Vaqt va hajm bo’yicha 
qiyinchiliklar
.
”mavzusidagi
 
MUSTAQIL 
ISH
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


MAVZU: Agoritm murakkabligini static va dinamik o’lchovlari. Vaqt va 
hajm bo’yicha qiyinchiliklar 
Mavjud algoritmlarning ko’pchilig xotira va tezlik o’rtasida tanlovni taklif qiladi. 
Masala tez ishlashi va katta xotira egallashi yoki sekin ishlashi va kichik xotira 
hajmini egallashi mumkin. Bu holatda eng odatiy misollardan biri eng qisqa 
masofani topish masalasi bo’la oladi. Bunda siz o’zaro bog’liq bo’lgan 
shahar orasidagi istalgan ikki nuqta orasidagi eng qisqa kerak bo’ladi. Bunda biz 
barcha 
nuqtalar orasidagi qisqa 
masofalarni 
aniqlab 
ularni 
jadval 
shaklida saqlab qo’yishimiz mumkin. Va biz eng qisqa masofani aniqlashimizga 
to’g’ri kelganda 
shunchaki jadvaldan 
ma’lumotni olib 
qo’yishimiz 
mumkin bo’ladi.
Natijani shu zahoti olishimiz mumkin, ammo bu juda katta hajm talab qiladi. 
Masalan 
biror katta 
xaritada 
10 
minglab 
nuqtalar bo’lishi mumkin va 
bizning jadvalimiz buning 
uchun 
10 
milliarddan 
ortiq 
ma’lumotni saqlashiga to’g’ri keladi va bu taxminan 10GB ga yaqin xotirani band 
etishi mumkin.
Ushbu holatdan hajm-vaqt murakkabligi kelib chiqadi. Shunda algoritm vaqt 
bo’yicha ishlash tezligi yoki hajm bo’yicha ishlash tezligi bilan baholanadi.
Biz asosiy e’tiborni vaqt bo’yicha murakkablikka qaratamiz lekin shu bilan birga 
foydalaniladigan xotira hajmini ham aniq belgilashimizga to’g’ri keladi.
2.Algoritmlarni eng yomon va o’rtacha holatlarda baholash Bitta masalani hal qilish 
uchun turli xil algoritmlarni ko'rib chiqsak, ular qancha hisoblash resurslarini 
(ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash 
foydalidir. Albatta, biz hisoblashning qaysi turidan foydalanilganligi to'g'risida 
kelishib olishimiz kerak .. Algoritmning ishlash vaqti bilan biz bajaradigan 
elementar qadamlar sonini tushunamiz. Aytaylik, psevdokodning bir qatorida 
belgilangan miqdordagi operatsiyalar talab qilinadi (masalan, ba'zi murakkab 


harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x-koordinata 
bo'yicha saralash"). Qo'ng'iroq qilish (qo'ng'iroq qilish) protsedurasini (ma'lum 
miqdordagi operatsiyalarni oladi) va uning bajarilishini (bajarilishini) farqlashingiz 
kerak, ular uzoq davom etishi mumkin. 
Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan 
manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan qiymatdir. 
Shunday qilib, biz algoritmning vaqtinchalik T (n) va fazoviy V (n) murakkabligini 
ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz vaqtinchalik 
murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga o'xshash tarzda 
baholanadi. Baholashning eng oson usuli bu eksperimental usul, ya'ni algoritmni 
dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha bajarish, 
dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator kamchiliklarga 
ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Ikkinchidan, 
shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi omillar ta'sir 
qiladi: 
. Dastur algoritmining vaqt murakkabligi; 
2. bajariladigan dasturning kompilyatsiya qilingan kodining sifati; 
3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari. 
Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligini 
o'lchashning tipik birliklaridan foydalanishga imkon bermaydi (soniya, 
millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (har bir algoritmni 
kim dasturlasa) bir xil algoritm uchun har xil baholarni olish mumkin. o'z), turli xil 
kompilyatorlar va turli xil kompyuterlar. 
Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda 
algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n) tartibiga 
to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. 


Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga 
murojaat qilishadi. 
Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan 
hisoblaydigan usul mavjud. 
3.Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va 
logarifmik solishtirma mezonlar 
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib 
borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini 
aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur 
bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish 
bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi" 
iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda, yaxshi 
bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan 
foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda 
foydali misolini ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) 
asosida amalga oshirish. 
Asosiy maqsad - hisoblash muammolarining samarali algoritmlarini izlash. Ushbu 
umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu mavzu bilan 
bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan qanday farq qiladi? 
Algoritmlarni ishlab chiqishda umumiy mavzular va loyihalash tamoyillarini 
aniqlashga harakat qilamiz. Bizni samarali algoritmlarni loyihalashning asosiy 
usullarini minimal ma'lumot bilan namoyish etuvchi paradigmatik masalalar va 
usullar qiziqtiradi. 
Algoritmni bajarilish qadami - bu ijrochi tomonidan bitta ko‘rsatmaning 
bajarilishidir. Bir masalani hal etuvchi ikkita 

Download 432,32 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish