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
