Mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari. Bajardi: Abdusattorov Anvar; Tekshirdi: Begimov O’ktam

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:



<sub>yoki



Bu formula integeralarni taqribiy hisoblashning to’g’ri turtburchaqlar formulasi.


bu formula itegrallarni taqribiy hisoblashning trapetsiya formulasi.


ya‘ni



bu yerda</sub>


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.
Algoritm tushunchasi va uning ta’rifi.
Har qanday dasturchi uchun algoritmlar nazariyasining asoslarini bilish juda muhim, 
chunki algoritmlarning umumiy xususiyatlarini va ularni namoyish etish uchun rasmiy 
modellarni o'rganadigan fan. Hatto informatika darslaridan bizga kelajakda maktabga 
qaraganda murakkabroq topshiriqlarni yozishda yordam beradigan oqim jadvallarini 
tuzishga o'rgatiladi. Hech kimga sir emaski, deyarli har doim ma'lum bir muammoni hal 
qilishning bir necha yo'li mavjud: kimdir ko'p vaqt sarflashni, boshqalari resurslarni 
sarflashni o'z ichiga oladi, boshqalari esa deyarli echim topishga yordam beradi. 
Siz har doim vazifaga muvofiq, xususan, muammolar sinfini hal qilish algoritmlarini 


ishlab chiqishda eng maqbul variantni izlashingiz kerak. 
Shuningdek, algoritm turli xil hajmlar va miqdorlarning boshlang'ich qiymatlarida o'zini 
qanday tutishi, unga qanday resurslar kerakligi va yakuniy natijani olish uchun qancha 
vaqt kerakligini baholash ham muhimdir.

Algoritm tushunchasi va uning ta’rifi. 

Ma'lumotni qayta ishlash algoritmi - bu kompyuter fanida muammoni hal qilish 
usulining tavsifi bo'lib, uni keyinchalik tanlangan dasturlash muhitida amalga oshirish 
mumkin. 

Algoritmni tahlil qilish - bu baholashni o'rganadigan informatika sohasidirishlash 

algoritmlari . 

Algoritmning murakkabligi bu algoritmni tahlil qilishda hisobga olinadigan 

elementar operatsiyalar sonidir. 
Algoritmning kapasitiv murakkabligi bu algoritmning eng yomon holatdagi xotira 
funktsiyasini asimptotik baholashdir. 

Algoritmning eng yomon, o'rta va eng yaxshi holatlaridagi resurslarning 

murakkabligi vaqt va funktsiyalar sinflarining tartiblangan juftligi.asemptomatik belgi 
bilan aniqlanadigan va ko'rib chiqilayotgan holatga mos keladigan sig'im murakkabligi . 
Ma'lumotlar tuzilmalari bilan ishlash algoritmlari bu olinadigan asosiy tamoyillar va 
metodologiyani aniqlaydigan algoritmlardirma'lumotlarni qayta ishlash 
usullarini tushunish . 
Saralash algoritmlari massivlar va fayllarni tartibga solish uchun mo'ljallangan 
algoritmlardir. 
Qidiruv algoritmlari bu katta ma'lumotlar to'plamida ma'lum elementlarni qidirish 
uchun mo'ljallangan algoritmlar. 
Graf algoritmlari bu amalga oshirish uchun mo'ljallangan 
algoritmlardirgrafik ayirish va qidirish strategiyalari . 
Simlarni qayta ishlash algoritmlari bu belgilar ketma-ketligini qayta ishlash uchun bir 
qator usullarni o'z ichiga olgan algoritmlardir. 
Geometrik algoritmlar bu geometrik ob'ektlardan foydalangan holda muammolarni 
echish uchun algoritmlardir. 
Algoritmni baholash Algoritmning murakkabligini o'lchashning bir necha usullari mavjud. Dasturchilar odatda algoritm tezligiga e'tibor qaratishadi, ammo boshqa ko'rsatkichlar ham bir xil ahamiyatga ega - xotira hajmiga, diskdagi bo'sh joyga talablar. Tez algoritmdan foydalanish, agar kompyuter ishlashi kerak bo'lganidan ko'proq xotirani talab qilsa, kutilgan natijalarga olib kelmaydi.
Xotira yoki vaqt Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. Muammoni tezroq, katta hajmdagi xotiradan foydalangan holda yoki ozroq hajmni olib, sekinroq hal qilish mumkin. Bu holatda odatiy misol eng qisqa yo'llarni qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini taqdim etib, siz ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng qisqa masofani aniqlash uchun algoritm yozishingiz mumkin. Bu masofalarni kerak bo'lganda hisoblamaslik uchun barcha nuqtalar orasidagi eng qisqa masofani ko'rsatib, natijalarni jadvalga saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa masofani aniqlashimiz kerak bo'lsa, bizshunchaki jadvalning tugagan masofasini olishimiz mumkin. Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, yuqorida tavsiflangan 
jadvalda10 milliarddan ortiq hujayralar bo'lishi kerak. Bular Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb xotirani ishlatish kerak. Ushbu qaramlikdan kosmik-vaqt murakkabligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan, algoritm bajarilihtezligi va iste'mol qilinadigan xotira nuqtai nazaridan baholanadi. Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol qilingan xotiraning hajmini aniq belgilaymiz. 
Buyurtmani baholash 
Turli xil algoritmlarni taqqoslashda ularning murakkabligi kirish ma'lumotlari 
miqdoriga bog'liqligini bilish muhimdir. Masalan, bitta usul yordamida saralashda ming sonlarni qayta ishlash 1 s., Va million sonlarni qayta ishlash uchun 10 s vaqt kerak bo'ladi, boshqa algoritmdan foydalanish esa 2 s vaqtni talab qilishi mumkin. va 5 s. navbati bilan Bunday sharoitda qaysi algoritm yaxshiroq ekanligini aniq aytish mumkin emas. 
Umumiy holda, algoritmning murakkabligini kattalik tartibida baholash mumkin. Agar kirish ma'lumotlarining o'lchamlari oshgani sayin, algoritmning bajarilish vaqti f (N) funktsiyasi bilan bir xil tezlikda oshsa, algoritmda O (f (n)) murakkablik bor. A [NxN] matritsasi uchun har bir satrda maksimal elementni topadigan kodni ko'rib chiqing. 
for i:=1 to N do 
begin 

max:=A[i,1]; 

for j:=1 to N do 
begin 
if A[i,j]>max then 

max:=A[i,j] 

Ushbu algoritmda i o'zgaruvchisi 1 dan N.gacha o'zgaradi, i ning har bir o'zgarishi bilan birga, j o'zgaruvchisi ham 1 dan N ga o'zgaradi. Tashqi aylanishning har bir N takrorlanishida ichki pastadir ham N marta bajariladi. Ichki pastadir takrorlanishlarining 
umumiy soni N * N dir. Bu O (N ^ 2) algoritmining murakkabligini aniqlaydi. 
Algoritmning murakkablik tartibini taxmin qilishda faqat eng tez o'sadigan qismda
foydalanish kerak. Vazifalar aylanishi N ^ 3 + N ifodasi bilan tasvirlangan deb taxmin qiling. Bunday holda, uning murakkabligi O ga teng bo'ladi (N ^ 3). Funktsiyaning tez o'sib boruvchi qismini ko'rib chiqish, algoritmning xatti-harakatlarini N.ning ortishi bilan baholashga imkon beradi. Masalan, N = 100 bilan N ^ 3 + N = 1000100 va N = 1000000 o'rtasidagi farq atigi 100 ga teng, bu 0,01%. O ni hisoblashda, ifodalarda doimiy omillarga e'tibor bermaslik mumkin. 3N ^ 3 ish bosqichiga ega bo'lgan algoritm O (N ^ 3) deb hisoblanadi. Bu O (N) nisbati muammoning hajmiga bog'liqligini yanada aniqroq qiladi. 
Qiyinchilikni aniqlash
Dasturning eng murakkab qismlari odatda pastadir va qo'ng'iroq qilish protseduralari. 
Oldingi misolda butun algoritm ikki tsikl yordamida amalga oshirildi. 
Agar bitta protsedura boshqasini chaqirsa, u holda protseduraning murakkabligini 
batafsilroq baholash kerak. Agar unda muayyan miqdordagi ko'rsatmalar bajarilgan 
bo'lsa (masalan, bosib chiqarish), unda bu murakkablikni baholashga deyarli ta'sir 
qilmaydi. Agar O (N) bosqichlar chaqirilayotgan protsedurada bajarilsa, funktsiya 
algoritmni sezilarli darajada murakkablashtirishi mumkin. Agar protsedura ko'chadan 
ichkarisiga chaqirilsa, u holda ta'sir yanada katta bo'lishi mumkin. 
Misol tariqasida ikkita protsedurani ko'rib chiqing: O (N ^ 3) murakkabligi bilan sekin 
va O (N ^ 2) murakkabligi bilan. 
Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal qilish uchun zarur 
bo'lgan vaqt va talab qilinadigan xotira miqdori hisoblanadi. 
Shuningdek, topshiriqlar sinfi uchun murakkablikni tahlil qilganda ma'lum bir 
ma'lumotni - kirish hajmini tavsiflovchi ma'lum bir raqam aniqlanadi . 
Shunday qilib, algoritmning murakkabligi kirish hajmining funktsiyasi degan xulosaga 
kelishimiz mumkin . 
Algoritmning murakkabligi bir xil kirish hajmi bilan farq qilishi mumkin, ammo har xil 
kirish ma'lumotlari. Eng yomon , o'rta yoki eng yaxshi holatda 
murakkablik tushunchalari mavjud . Odatda, eng yomon ishning murakkabligi 

baholanadi. Vaqtning murakkabligi 
eng yomon holatda, berilgan o'lchamdagi masalani echishda algoritmni bajarish paytida 
bajariladigan operatsiyalarning maksimal soniga teng bo'lgan kirish hajmining 
funktsiyasi. Eng yomon holatda, 

kapasitiv murakkablik bu o'lchamdagi muammolarni echishda foydalanilgan xotira 
hujayralarining maksimal soniga teng kirish hajmi funktsiyasidir.