Mavzu: Normal va murakkab algoritmlar (4 soat) Reja

3. Algoritmlar murakkabligi


Algoritmlarning murakkabligi. Hisoblash muammolari cheklangan xotira resurslaridan foydalangan holda oqilona vaqt ichida yechilishi kerak. Bu algoritmning vaqt va fazoviy murakkabligi tushunchasiga olib keladi. Qoida tariqasida, algoritm turli vaqtlarni bajarishi mumkin boʻlgan turli xil amallarni oʻz ichiga oladi.
Algoritmlarni baholash uchun koʻpgina mezonlar mavjud. Odatda
kirituvchi berilganlarni koʻpayishida masalani yechish uchun kerak
boʻladigan vaqt va xotira hajmlarini oʻsish tartibini aniqlash muammosi
qoʻyiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini
aniqlovchi qandaydir sonni bogʻlash zarur. Bunday son masalaning
kattaligi deb qabul qilinadi. Masalan, ikkita matritsani koʻpaytirish
masalasining oʻlchami boʻlib, matritsalar kattaligig xizmat qilishi
mumkin. Graflar haqidagi masalada oʻlcham sifatida graf uchlarining
soni boʻlishi mumkin.
Algoritm sarflanayotgan vaqt masalaning oʻlchami funksiyasi
sifatida algoritmni vaqt boʻyicha qiyinligi deb nomlanadi. Bunday
funksiyaga masalaning kattaligi oshganda limit ostidagi oʻzgarish
asimptotik qiyinlik deb aytiladi.
Murakkablikni baholash. Algoritmlarning murakkabligi odatda
bajarilish vaqti yoki ishlatilgan xotira boʻyicha baholanadi. Ikkala
holatda ham, murakkablik kiritilgan ma‘lumotlarning hajmiga bogʻliq:
100 ta elementdan iborat massivi xuddi shunga oʻxshash 1000 ta
elementdan iborat massivga qaraganda tezroq qayta ishlanadi. Shu bilan
birga, aniq vaqt bilan bir necha kishi qiziqadi: bu protsessorga bogʻliq, ma‘lumotlar turi, dasturlash tili va boshqa koʻplab parametrlarga ham
bogʻliq. Faqatgina asimptotik murakkablik muhim, ya‘ni kirish
ma‘lumotlarining kattaligi cheksizlikka intilayotgandagi murakkablik.