Agoritm murakkabligini static va dinamik o’lchovlari. Vaqt va hajm bo’yicha qiyinchiliklar

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 masofani topishingiz
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 -=ABX.=-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 algoritmdan kam qadam talab qilinayotgani samaraliroqdir. Samaradorlik o‘lchovi - bu bor-yo‘g‘i qadamlar sonidir. Lekin chuqurroq e’tibor berib qarasak, bu ta’rifdagi mujmal tomonlarni aniqlaymiz. Ba’zan avval uchragan algoritmlardagidan ko‘ra vaziyat murakkabroq bo’ladi.
Algoritmlar murakkabligi bilan ham farqlanishi mumkin. Algoritmning murakkabligini uning matnidagi satrlar soni bilan o‘lchaymiz. Shu bilan birga quyidagi ikki satrni bir tuzilmaning ikki qismi bo‘lgani uchun bittaga hisoblaymiz
4.Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash
Oliy matematika kursidan malumki aniq integrallar asosan N‘yuton-Leybnits formulasi bilan hisoblanadi. Yani quyidagi formula bilan hisoblanadi:

Bu yerda F(x) funktsiya f(x) funktsiyaning boshlangich funktsiyasi. а-integralning quyi b-esa yuqori chegarsi. Nyuton–Leybnits formulasi bizga ma‘lumki elementar funktsiyalar uchun foydalanish qulayrok.

Lekin har qanday f(x) funktsiyaning boshlangich funktsiyasi elementar funktsiya bulavermaydi, yani integrallash murakkab bo’ladi. Bunday aniq integrallarni N‘yuton-Leybnits formulasi bilan hisoblab bulmaydi. Bunday hollarda integrallarni taqribiy hisoblash usularidan foydalanib integrallarning taqribiy kiymatlari topiladi.
Aniq integralni taqribiy hisoblash usullari
Odatda aniq integralarni taqribiy hisoblash uchun integralash sohasidagi [a,b] kesma n ta teng bo’lakka bulinadi. Har bir bo’lakning uzunligi h=(b-a)/n formula bilan hisoblanadi.
n bo’laqlar soni qancha ko’p bo’lsa integralning kiymati shuncha aniq bo’ladi. Integralarni taqribiy hisoblashda ko’pincha to’g’ri burchaqlar, trapetsiyalar va Simpson formulalaridan foydalaniladi. Integrallarning kiymatlarini taqribiy hisoblash uchun biror bir usul tallanadi, sung algoritm tuziladi va bu algoritmlarga mos ravishda biror bir dasturlashtirish tilida dasturlar tuzilib, dasturlar kompyuterga kiritilib natijalar olinadi.
Integrallarning taqribiy hisoblash formulalarini keltirib chiqarish ishlarini ko’rib o’tirmaymiz, bu bizga oliy matematika kursidan ma‘lum. Formulalarning keltirib chiqarish ma‘lumotlarini o’quvchilarga berilgan adabiyotlardan [11] adabiyotdan ukib olishlarini tavsiya etamiz.
Integralning kiymatini taqribiy xisolash formulalarini keltiramiz:
yokiBu formula integeralarni taqribiy hisoblashning to’g’ri turtburchaqlar formulasi.
bu formula itegrallarni taqribiy hisoblashning trapetsiya formulasi.
ya‘nibu yerda
Bu formula esa aniq integralni taqribiy hisoblashning Simpson formulasi.
Aniq integralni Simpson usulida hisoblaganda taqribiy hisoblash xatoligi boshqa usullarga nisbatan kamrok, yani aniqlik kattarok bo’ladi
Algoritmning operatsion murakkabligini baholash
Algoritmning murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida aniqlash mumkin. Loopsiz va rekursiv chaqiruvlarsiz algoritmlar doimiy murakkablikka ega. Shuning uchun algoritmning murakkabligini aniqlash asosan tsikllar va rekursiv chaqiruvlarni tahlil qilishga qisqartiriladi.
O'chirish algoritmini ko'rib chiqing Kimga o'lcham massividan th element P dan harakatlanuvchi massiv elementlaridan iborat (k + 1) dan P-massiv boshiga qaytish va elementlar sonini kamaytirish P birlik uchun. Massivni qayta ishlash siklining murakkabligi Oh (p-k) pastadir tanasi (harakat qilish operatsiyasi) bajarilganligi sababli Kompyuter marta, va pastadir tanasining murakkabligi 0 (1), ya'ni. doimiydir.

Ko'rib chiqilayotgan misolda murakkablik asimptotik 0 (") bilan tavsiflanadi, chunki bu algoritmda bajariladigan operatsiyalar soni ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas. Murakkablik funktsiyasi deterministik bo'lib, asimptotikaning barcha turlari bir-biriga to'g'ri keladi: f (n) = Q (n-k), f (n) = 0 (n-k) va f (n) = Q (n-dan). Bu fakt © () belgisi bilan tasdiqlanadi. 0 (*) va/yoki 2 (*) dan faqat ushbu asimptotiklar boshqacha bo'lsa foydalanish kerak.

Loop turi (for, while, takrorlash) murakkablikka ta'sir qilmaydi. Agar bir sikl boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi. Takroriy uyalar qiyinchilikni oshiradigan asosiy omil hisoblanadi. Misol tariqasida, biz o'lchamdagi massiv uchun taniqli qidirish va saralash algoritmlarining murakkabligini keltiramiz. P:
ketma-ket qidiruvda taqqoslash operatsiyalari soni: 0 (i);
Ikkilik qidiruvda taqqoslash operatsiyalari soni: 0 (log 2 P);
oddiy almashuv usulida taqqoslash operatsiyalari soni (qabariqli tartiblash): 0 (i 2);
pufakchali tartibdagi almashtirish operatsiyalari soni: 0 (n 2);
E'tibor bering, oddiy almashish usulida taqqoslash operatsiyalari soni asimptotikaga ega 0 (n 2) va almashtirish operatsiyalari soni ikki xil asimptotikaga ega 0 (n 2) va? 2 (0), chunki taqqoslashlar soni saralangan ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas, almashtirishlar soni esa ushbu o'ziga xoslik bilan aniq belgilanadi. O'zgartirishlar umuman amalga oshirilmasligi mumkin - agar ma'lumotlar qatori dastlab to'g'ri tartiblangan bo'lsa yoki almashtirishlar soni maksimal bo'lishi mumkin - taxminan P 2, - agar tartiblangan massiv dastlab teskari yo'nalishda tartiblangan bo'lsa.
Funktsiya nomi g (n) asimptotikada f (n) = @ (t (n)) va f (a) = 0 (g (n)) algoritmni tavsiflash uchun murakkablik funksiyasi / (") ishlatiladi. Shunday qilib, polinom, eksponensial, logarifmik va hokazo murakkablik algoritmlari haqida gapiriladi.