Mavzu:
Algoritm murakkabligining statik va dinamik o‘lchovlari. Vaqt va
xotira hajmi bo‘yicha qiyinchiliklar
Reja:
1
Algoritm murakkabligining statik va dinamik o‘lchovlari. Vaqt va xotira
hajmi bo‘yicha
qiyinchiliklar
2
Algoritmlarni eng yomon va o‘rtacha holatlarda baholash.
3
Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logorifmik
solishtirma mezonlari.
4
Ketma – ketliklar, to’plamlar, daraxtlar, graflarniifodalashusullari.
5
Taqribiyintegrallashusullarinianiqligivahisoblashhajmibo‘yichataqqoslash.
6
Algebraikvatranstsendenttenglamalarnitaqribiyyechishusullariniyaqinlashish
tezligibo‘yichabaholash.
7
Chiziqli algebraik tenglamalar sistemalarini taqribiy yechish usullari.
Yaqinlashishshartlari.
.
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.
Doimiy
vaqt
Algoritmga algoritm deyiladi doimiy vaqt(vaqt sifatida qayd etilgan O (1))
qiymat bo'lsa T(n) kirish hajmiga bog'liq bo'lmagan
qiymat bilan
cheklangan. Masalan, massivda bitta elementni olish doimiy vaqtni oladi,
chunki uni topish uchun bitta buyruq bajariladi. Biroq, tartiblanmagan
massivda minimal qiymatni topish doimiy vaqtdagi operatsiya emas, chunki
biz massivning har bir elementini skanerlashimiz kerak.
Shunday qilib, bu
operatsiya chiziqli vaqtni oladi, O (n). Agar elementlarning
soni oldindan
ma'lum bo'lsa va o'zgarmasa, bunday algoritmni doimiy vaqt algoritmi deb
atash
mumkin.
"Doimiy vaqt" nomiga qaramay, ish vaqti vazifa hajmidan mustaqil bo'lishi
shart emas, lekin ish vaqtining yuqori chegarasi bo'lmasligi kerak. Masalan,
"qiymatlarni almashish"
vazifasi a va b, zarur bo'lsa, natijada biz olamiz
a≤b", doimiy vaqt muammosi hisoblanadi, garchi algoritmning ishlash vaqti
tengsizlikning mavjudligiga bog'liq bo'lishi mumkin. a ≤ b yoki yo'q. Biroq,
ma'lum bir doimiylik mavjud t, ular uchun vazifani bajarish vaqti har doim
oshmaydi
t.
Quyida doimiy vaqtda ishlaydigan ba'zi kod misollari keltirilgan:
Int indeksi = 5; int element = ro'yxat; agar(shart to'g'ri) keyinboshqa doimiy
ish vaqti bilan ba'zi operatsiyalarni bajarish uchun i = 1 uchun 100 uchun j =
1 uchun 200 doimiy ish vaqti bilan ba'zi
operatsiyalarni bajaradi
Agar T(n) bu O ( ba'zi doimiy qiymat), bu ga teng T(n) O (1) dir
Algoritmga
algoritm deyiladi
