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

Algoritmlar murakkabligining oʻsish tartibi
Murakkablikning oʻsish tartibi (yoki aksiomatik murakkablik) katta kirish hajmi uchun algoritmning murakkablik funksiyasining taxminiy xatti-harakatini tavsiflaydi. Bundan kelib chiqadiki, vaqt murakkabligini baholashda elementar amallarni koʻrib chiqishning hojati yoʻq, algoritm qadamlarini koʻrib chiqish kifoya.
Algoritm qadami – bu ketma-ket joylashtirilgan elementar amallar toʻplami, uning bajarilish vaqti kirish qadamiga bogʻliq emas, ya‘ni yuqoridan qandaydir doimiy bilan chegaralangan.
Asimptotik baholashning koʻrinishlari. F(n)>0 murakkabligini, bir xil tartibdagi g(n)>0 funksiyasini, kirish n>0 oʻlchamini koʻrib chiqaylik.
Agar f(n) = O (g(n)) va n> n0 uchun c>0, n0> 0 konstantalar mavjud boʻlsa, u holda 0 18
Bu holda g(n) funksiyasi f(n) uchun asimptotik-aniq baho hisoblanadi. Agar f(n) algoritmning murakkablik funksiyasi boʻlsa, unda murakkablik tartibi f(n) uchun - O(g(n)) deb belgilanadi. Ushbu ibora doimiy koeffitsiyentgacha g(n) dan tez oʻsmaydigan funksiyalar sinfini belgilaydi.
1-jadval.
Asimptotik funksiyalarga misollar
1.4. Algoritmlarning yomon, oʻrta, yaxshi holatlari tushunchalari
Algoritm murakkabligining oʻsish tartibi O(n) deb aytganda nimani nazarda tutamiz? Bu oʻrtacha? Yoki eng yomoni? Ehtimol, eng yaxshisi?
Agar eng yomon holat va oʻrtacha koʻrsatkichlar bir-biridan farq qilmasa, odatda, eng yomon holat nazarda tutiladi. Masalan, biz oʻrtacha O(1) oʻsadigan, lekin vaqti-vaqti bilan O(n) ga aylanadigan algoritmlarning misollarini koʻrib chiqamiz (masalan, massivga element qoʻshish). Bunday holda, algoritm oʻrtacha vaqt ichida doimiy ishlashini koʻrsatamiz va murakkablik oshadigan holatlarni tushuntiramiz.
Algoritmlar va ma‘lumotlar tuzilmalarining murakkabligini oʻlchashda odatda ikkita narsa haqida gaplashamiz: ishni bajarish uchun zarur boʻlgan amallar soni (hisoblash murakkabligi) va algoritm zarur boʻlgan resurslar, xususan, xotira (fazoviy murakkablik).
Oʻn baravar tezroq ishlaydigan, ammo oʻn barobar koʻproq joy ishlatadigan algoritm koʻproq xotirali server mashinasi uchun yaxshi f(n) g(n)
8
1
19
boʻlishi mumkin. Ammo xotira hajmi chekli oʻrnatilgan tizimlarda ushbu algoritmdan foydalanib boʻlmaydi.
Odatda, quyidagi amallar hisobga olinadi:
1) taqqoslashlar ("katta", "kichik", "teng");
2) oʻzlashtirish (ta‘minlash);
3) xotira ajratish.
Qaysi amalni hisoblash esa, odatda kontekstda aniqlanadi.
Masalan, ma‘lumotlar tarkibidagi elementni topish algoritmini tavsiflashda biz deyarli taqqoslash amallarini nazarda tutamiz. Qidirish, avvalambor, oʻqish jarayonidir, shuning uchun ta‘minlash yoki xotira ajratishda hech qanday ma‘no yoʻq.
Tartiblash haqida gapirganda esa, taqqoslash, xotira ajratish va ta‘minlash amallarini hisobga olishimiz mumkin. Bunday hollarda biz qaysi amallarni koʻrib chiqayotganimizni aniq koʻrsatib beramiz.
Algoritmlar nazariyasining asoslarini bilish har qanday dasturchi uchun juda muhimdir, chunki aynan shu fan algoritmlarning umumiy xususiyatlarini va ularni namoyish etishning rasmiy modellarini oʻrganadi. Hatto informatika darslaridan boshlab ham bizga jadvallarni tuzishni oʻrgatmoqdalar, bu keyinchalik maktabga qaraganda ancha murakkab masalalarni yozishda yordam beradi. Bundan tashqari, ma‘lum bir muammoni hal qilishning deyarli har doim bir necha yoʻli borligi sir emas: ba‘zilari koʻp vaqt, boshqa resurslarni sarflashni oʻz ichiga oladi, boshqalari esa faqat taxminiy yechim topishga yordam beradi.
Siz har doim topshiriqqa muvofiq ravishda eng maqbul narsani izlashingiz lozim, xususan, muammolar sinfini hal qilish algoritmlarini ishlab chiqishda.
Algoritmni har xil hajm va miqdorlarning boshlangʻich qiymatlari bilan qanday ishlashini, qanday manbalarga ehtiyoj borligini va yakuniy natijani chiqarish uchun qancha vaqt ketishini baholash ham muhimdir.
Koʻpincha, algoritm tahlili bir xil masalani yechish uchun ikki xil algoritmlarni taqqoslash yoki algoritmning amaliy qoʻllanilishini aniqlash uchun ishlatiladi. Algoritmlarni bajarish vaqti boʻyicha baholashga toʻxtalamiz. Algoritmlarni bajarish vaqtiga qarab
20
baholashning yondashuvlaridan biri bu algoritmni oddiygina kompyuterda ishga tushirish va uni u yoki bu tarzda vaqtga solishdir.
Ushbu yondashuvning koʻplab kamchiliklari mavjud. Birinchidan, bajarish vaqti algoritm ishlayotgan kompyuterga juda bogʻliq. Ikkinchidan, bunday taxmin kiritish ma‘lumotlarining ma‘lum bir oʻlchovi uchun faqat bitta qiymatni beradi. Agar bizda har xil oʻlchovlar boʻyicha taxminiy jadval mavjud boʻlsa ham, undan ish vaqtining kirish ma‘lumotlarining oʻlchamiga funksional bogʻliqligini olish juda muammoli.
Shuning uchun algoritmni bajarilish vaqti boʻyicha baholash uchun kirish ma‘lumotlarining oʻlchamlari boʻyicha bajarilgan elementar amallar sonining funksional bogʻliqligini topishga harakat qilishdir.
Algoritm murakkabligining asosiy koʻrsatkichi bu muammoni hal qilish uchun sarflanadigan vaqt va kerakli xotira hajmi.
Shuningdek, muammolar sinfi uchun murakkablikni tahlil qilishda ma‘lum bir ma‘lumot miqdori - kirish kattaligini tavsiflovchi ma‘lum bir raqam aniqlanadi. Shunday qilib, biz algoritmning murakkabligi kirish oʻlchamining funksiyasi degan xulosaga kelishimiz mumkin.