Algoritm-1must pdf

Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va logarifmik solishtirma mezonlar.

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, biz shunchaki 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

jadvalda 10 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 bajarilish tezligi va iste'mol qilinadigan xotira nuqtai nazaridan

baholanadi.

Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol

qilingan xotiraning hajmini aniq belgilaymiz.

4. Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash

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:

yoki

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

bu formula itegrallarni taqribiy hisoblashning trapetsiya formulasi.
ya‘ni

bu yerda

Bu formula esa aniq integralni taqribiy hisoblashning Simpson formulasi