|
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 turlari
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
Vaqtning murakkabligi logarifmik og'irlik mezoni bilan
Ushbu paragrafda baholanishi kerak bo'lgan operatsiyalar ko'rsatilishi
kerak. Birinchidan, bu taqqoslash operatsiyalari. Ikkinchidan, o'zgaruvchan parametrlarning ishlashi (qo'shish, ko'paytirish). Belgilanish operatsiyalari 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 qiymatni 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 modelidan foydalanilganligi to'g'risida kelishib olishimiz kerak. Ushbu ta'lim, bir model sifatida, eng qismi uchun, biz oddiy bir protsessor 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'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, 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.
XULOSA
Eslatib o'tamiz, rekursiv protseduralar o'zlarini chaqiradigan protseduralardir. Ularning
qiyinligini aniqlash juda qiyin. Ushbu algoritmlarning murakkabligi nafaqat ichki
pastadirlarning murakkabligiga, balki rekursionning takrorlanish soniga
bog'liq. Rekursiv protsedura etarlicha sodda ko'rinishi mumkin, ammo dasturni qayta-
qayta chaqirib, dasturni jiddiy ravishda murakkablashtirishi mumkin.
Faktorial hisoblashning rekursiv amalga oshirilishini ko'rib chiqing: Ushbu protsedura
N marta bajariladi, shuning uchun ushbu algoritmning hisoblash murakkabligi O (N)
dir.
Shunday qilib, kompyuterlarning turli xil variantlari eng oddiy Tyuring mashinalaridan bir hil hisoblash muhitigacha ko'rib chiqiladi. Ularning barchasi algoritm mavjud bo'lgan muammolarni hal qilish uchun ishlatilishi mumkin.
FOYDALANILGAN ADABIYOTLAR
1. Maxmudov M.X. Kutubxona-axborot faoliyatini boshqarish: Darslik. Toshkent., 2009.-505 b.
2.Pedagogika. Ensiklopediya 1–jild. Toshkent.: О‘zbekiston milliy ensiklopediyasi, 2015 yil. – 318 bet.
3.Pedagogika Ensiklopediya 2–jild, Toshkent.: О‘zbekiston milliy ensiklopediyasi, 2015 yil. – 374 bet.
Do'stlaringiz bilan baham: |
