Samarqand davlat universiteti raqamli texnologiyalar fakulteti

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 tarkibiy qismlari 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 emas, balki uchta baho berishadi: 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. 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.

Shunday qilib, bizning algoritmimizning eng yaxshi bahosi 2n, eng yomoni esa 3n-1.