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

S=0; (1)
for(int i=0; i
S=S+A[i]; (n)
Barcha operatorlarning algoritmlar murakkabligi yigʻindisini hisoblash natijasida 2n + 2 murakkablikni olish mumkin.
Algoritmlarni baholashda koʻpincha quyidagi funksiyalar qoʻllaniladi: , n, , , , , , . koʻrinishida baholangan algoritmlar, har qanday sababga koʻra, juda tez algoritmlar deb nomlanadi. Bunday algoritmlar unchalik koʻp emas. Aslida, adabiyotda odatda O bahoga ega boʻlgan faqat bitta algoritm zikr qilinadi - bu ikkilik qidiruv algoritmi. Buni keyinroq koʻrib chiqamiz. va deb baholangan algoritmlar tezkor algoritmlar deb ataladi.
24
O(n2), O(n3) yoki umumiy holatda O(nC) boʻlgan algoritmlar polinomial algoritmlar deyiladi, O(2n), O(10n), O (n!) baholangan algoritmlar esa polinomial boʻlmagan algoritmlar deyiladi.
3-misol. Amaliy muhim masalalarning oʻlchamlari odatda ancha katta. Algoritmlarning misollarini koʻrib chiqamiz, ularning baholanishi nafaqat kirish ma‘lumotlarining oʻlchamiga bogʻliq. Bu bir oʻlchovli massivning elementlari orasida eng katta (eng kichik) qiymatni topish uchun keng qoʻllaniladigan algoritm:
(1) max = a[0]; 1
(2) for(int i=2; i<=n; i++) n
(3) if (max
(4) max = a[i]; 0 dan n-1 ta
Operatorlarning 1, 2 va 3 baholarini topish toʻgʻri boʻlishi kerak. Ammo 4-operatorning bajarilish soni massiv tarkibiy qismlarining oʻziga xos qiymatlariga bogʻliq, shuning uchun biz aniq baho berolmaymiz. Bunday holda, quyidagicha harakat qiling. Ular bitta baho bilan emas, balki uchta baho bilan baholanadi: eng yaxshi, eng yomon va oʻrtacha. Ushbu uchta baholashdan eng qiyini oʻrtacha qiymatni topishdir (hatto oʻrtacha nimani anglatishini shakllantirish ham), garchi amaliy nuqtai nazardan bu eng muhimi boʻlsa ham. Birinchi kurs talabalari uchun bu, ehtimol, qiyin muammo, shuning uchun biz bu yerda koʻrib chiqmaymiz.
Eng yaxshi va yomon baholarni topish osonroq. Tegishli operator mos ravishda eng kam va koʻp marta bajariladigan bunday kirish ma‘lumotlarini tasavvur qilish kerak.
Bizning misolimiz uchun eng yaxshi kirish ma‘lumoti birinchi raqami maksimal boʻlgan massiv boʻlishi mumkin. Bunday holda, 4-operator hech qachon bajarilmaydi, chunki 3-operatordagi shart har doim yolgʻon boʻladi. Eng yomon kirish ma‘lumotlari esa eng katta element eng oxirida boʻlgan massiv boʻlishi mumkin. Bunday holda, 3-operator shart har safar rost boʻladi va 4-operator har safar bajariladi.
25
Shunday qilib, bizning algoritmimizning eng yaxshi bahosi 2n, eng yomoni esa 3n-1.
4-misol. Ichki sikllarni oʻz ichiga olgan yanada murakkab algoritmlarni baholashning misoli sifatida koʻrib chiqamiz.
Masalaning sharti quyidagicha boʻlsin. a1, a2, ..., an butun sonlar massivi berilgan. Massiv tarkibiy qismlarini kamaymaydigan tartibda joylashtiring.
Birinchi algoritm massiv elementlarni tanlash usuli yordamida saralash. Uning mohiyati quyidagicha. Butun massivda minimal element qidiriladi va birinchi oʻringa qoʻyiladi, massivning qolgan qismida minimal qidiriladi va ikkinchi oʻringa qoʻyiladi va hokazo, massivning oxirgi elementi koʻrib chiqilmaguncha bu ish davom ettiriladi. Ushbu algoritmdan odamlar kundalik hayotda foydalanadilar. Bu algoritm ancha "yomon", ya‘ni samarasiz koʻrinadi. Keling, ushbu algoritmni batafsil koʻrib chiqaylik: