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

Algoritmni o'sish tartibi
Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik) katta
kirish o'lchamiga
ega bo'lgan algoritmning murakkablik funktsiyasining taxminiy xatti-hara
katlarini
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 turlari
O - eng yomon holat

---

F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchami
ni n> 0 ko'rib
chiqing .
Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , n
Vaqtning murakkabligi logarifmik og'irlik mezoni bilan
Ushbu paragrafda baholanishi kerak bo'lgan operatsiyalar ko'rsatilishi
kerak. Birinchidan, bu taqqoslash operatsiyalari. Ikkinchidan, o'zgaruvch
an parametrlarning ishlashi (qo'shish, ko'paytirish). Belgilanish operatsiya
lari hisobga olinmaydi, chunki u darhol sodir bo'ladi deb taxmin qilinadi.
Shunday qilib, ushbu vazifada uchta operatsiya ajratiladi
Logarifmik og'irlik mezoni bilan sig'im murakkabligi
Bunday holda, xotira hujayrasida bo'lishi mumkin bo'lgan maksimal qiym
atni
ko'rib
chiqing.
Agar
qiymat
aniqlanmasa
(masalan, operand i> 10 bilan), u
holda V maksimal
qiymatining chegarasi bor deb hisoblanadi .
Ushbu muammoda qiymati n (i) dan oshmaydigan o'zgaruvchi va
qiymati n dan
oshmaydigan o'zgaruvchi mavjud ! (natija) . Shunday qilib, bal O (log
(n!)) .
Algoritmlarning murakkabligini o'rganish juda qiziqarli vazifadir. Hozirgi
vaqtda eng
oddiy
algoritmlarning
tahlili
IT
sohasidagi
informatika
va amaliy matematikaga jalb
qilingan
texnik
mutaxassisliklar
o'quv
dasturiga
kiritilgan (aniqrog'i "Informatika va
kompyuter injiniringi" yo'nalishi).
Murakkablikka
qarab,
har
xil vazifalar sinflari ajralib chiqadi: P , NP , NPC . Ammo bu
endi algoritmlarni asimptotik tahlil qilish nazariyasi muammosi emas.
lgoritmlarning resurs samaradorligini baholash usullari
Asosiy algoritmik konstruktsiyalar protsessual dasturlash quyidagilardan
iborat:dallanma
va
pastadir.
Belgilangan
kirish
o'lchamiga
ega bo'lgan eng yaxshi, o'rta
va
eng
yomon
holatlar
uchun murakkablik funktsiyalarini olish uchun asosiy algoritmik
dizaynlarni baholashda farqlarni hisobga olish kerak.

---

Algoritmlarni tahlil qilish; eng yaxshi, eng yomon
va o'rtacha ish vaqti. Bitta
masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular
qancha hisoblash resurslarini (ishlash vaqti, xotira)
talab qilishini tahlil qilish va
eng samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelida
n foydalanilganligi to'g'risida kelishib olishimiz
kerak. Ushbu ta'lim, bir model sifatida, eng qismi uchun, biz oddiy bir pr
otsessor foydalanish tasodifiy kirish
mashinasi ( tasodifiy - kirish mashinasi , RAM operatsiyalar
parallel ijro uchun taqdim emas).
Ishlash vaqti ( ish vaqti ) algoritmi ostida biz bajaradigan elementar
qadamlar sonini anglatadi. Aytaylik, psevdokodning bir
qatorida belgilangan miqdordagi operatsiyalar talab etiladi (agar
ba'zi bir xatti-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 o'z ichiga olgan) va
uning bajarilishini ( bajarilishini ) uzoq vaqt davomida ajratib turishingiz
kerak .
Algoritmning murakkabligi bu vazifaning o'lchamiga
qarab talab qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimch
a
xotira) aks ettiradigan qiymatdir. Shunday qilib, biz algoritmning vaqtinc
halik T ( n ) va
fazoviy V ( n ) murakkabligini ajratamiz. Murakkablikni baholashni ko'ri
b chiqishda
biz vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ha
m shunga
o'xshash tarzda baholanadi. Baholashning eng oson usuli - bu eksperimen
tal, 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.

---