24
O(n
2
), O(n
3
) yoki umumiy holatda O(n
C
) 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
n-1
(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:
