Hisoblash modellari, algoritmlar va ularning murakkabligi Algoritm tushunchasi. Avvalo algoritm

Uchinchi yoʻnalish – Rossiya matematigi A.Markov4 tomonidan ishlab chiqilgan normal algoritmlar tushunchasi bilan bogʻliq.


Algoritmlarning 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,
4 Bu yerda bir xil Markov Andrey Andreyevich (Марков Андрей Андреевич) ism-sharifga ega Rossiya matematiklari ota-bola A. A. Markovlarning kichigi (1903-1979) nazarda tutilgan. Ensiklopediyalarda A. A. Markovlarning kattasini (1856-1922) rus, kichigini esa sovet matematigi deb ham atashadi.
16
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.
Masalan, ba‘zi bir algoritmga kirish ma‘lumotlarining n ta elementlarini qayta ishlash uchun 4n3 + 7n ta shartli amallarni bajarish kerak. n ning ortishi bilan ishning umumiy davomiyligi n ning kubi uni 4 ga koʻpaytirgandan yoki 7n ni qoʻshgandan koʻra koʻproq ta‘sir qiladi. Ushbu algoritmning vaqt murakkabligi O(n3), ya‘ni u kubik bilan kiritilgan ma‘lumotlarning hajmiga bogʻliq boʻladi.
Bosh harf O dan foydalanish matematikadan kelib chiqadi, bu yerda ushbu belgi funksiyalarning asimptotik harakatlarini taqqoslash uchun ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki egallagan xotira miqdori), kiritilgan ma‘lumotlarning hajmiga qarab, f(n) ga koʻpaytiriladigan ba‘zi konstantalardan tezroq emasligini anglatadi.