Reja Algoritmlar va ularning to’liq tuzulishining bosqichlari

TASVIRLARNI TANISH MASALASI
Masala qo’yilishi

Etalon bilan taqqoslash muammosining bir o’lchamli holatida tasvirlarni tanish masalalaridan quyidagisini ko’ramiz. Kirish ma’lumoti sifatida n ta haqiqiy sonlardan iborat X vektor berilgan. Chiqishda shu vektorning barcha uzluksiz qism vektorlari orasida maksimal elementlar yig’indini hosil qilish kerak.

Masalan, kirish vektori

31	-41	59	26	-53	58		97	-93		-23		84

bo’lsa, unda chiqishda X[3..7] vektorning 187 qiymatli yig’indisini hosil qilamiz. Bu yerda, agar kirish vektorida hamma sonlar musbat bo’lsa, masala osonlashadi; maksimal qism-vektor sifatida kirish vektorning o’zi xizmat qiladi. Agar X vektorda manfiy sonlar ham bo’lsa, masala qiyinlashadi.
Algoritmni tuzish

Masalani yechish uchun, barcha elementlari manfiy bo’lgan vektorda maksimal yig’indiga ega bo’lgan vektor-qismni bo’sh vektor, ya’ni elementlar yig’indisi nolga teng bo’lgan vektorni qabul qilish shartini kiritamiz.

Eng oddiy variantda algoritm shartini qanoatlantiruvchi barcha L va U butun sonlar juftliklari bo’yich X[L..U] vektorlari elementlari yig’indilarini hisoblab chiqadi va har qadamda topilgan yig’indi shungacha topilgan yig’indidan kattaligi tekshiriladi.
Psevdotilda dastur quyidagicha bo’ladi:
Maxsum:=0,0;
For L:=1 to N do
For U:=L to N do
Begin Sum:=0,0;
For i:=L to U do Sum:=Sum+x[i];
Maxsum:=max(maxsum, sum);
End.


Algoritm tahlili

Dasturning jiddiy kamchiligi – sekin ishlashi. 1990 yildagi o’rta tezlikka ega bo’lgan kompyuterlarda (286) N=1000 bo’lganda 1 soat, N=10000 bo’lganda 39 soat vaqtda bajarilgan. Bunday tezlikdagi dasturni qo’llab bo’lmaydi.

Algoritm samaradorligini intuntiv baholab ko’raylik. O-yozuvdan foydalanamiz. Eng tashqi siklning operatorlari aniq N marta bajariladi, o’rta siklning operatorlari tashqi siklning har bir qadami bo’yicha bajarilishi N dan oshmaydi. Demak, o’rta siklda bajarilayotgan 4 ta satr marta qiyinlik bilan baholanadi. Shu 4 ta satrlarda joylashgan sikl bajarilish soni ham N dan oshmaydi va O(N) bilan baholanadi. Baholarni ko’paytirish natijasida algoritmni umumiy bahosi proporsionalligini aniqlaymiz.
“O-yozuv” usulning kamchiligi shundaki – konkret berilganlar uchun dastur bajarilishiga aniq sarflanayotgan vaqtni hisoblab bilmaymiz, faqatgina qadamlar bajarilish soni bo’lganini bildik. Lekin bu usul bilan tahlil qilish qulay, va berilgan amaliy masala uchun dasturni samaradorligini aniqlaydigan dastlabki hisoblashlar uchun algoritmning isahlash vaqtini assimptotik bahosini beradi.
Shu tahlil yordamida quyidagi algoritm yuqoridagi masalani qadamlar bilan yechimini ko’rsatamiz.
Algoritm optimallashtirish

Bu algoritmda X[L..U] vektorning elementlar yig’indisi birinchi algoritmdagidek (U-L+1) qadamda emas, balki aniq sonli qadamlar bilan topiladi.

Yig’indini tez hisoblanishi X[L..U] vektorning elementlar yig’indisi, X[L..U-1] vektorning yig’indisiga bog’liqligiga asoslangan. Algoritm ko’rinishi quyidagicha:
Maxsum:=0,0;
For L:=1 to N do
Begin sum:=0,0;
For U:=L to N do sum:=sum+x[U];
Maxsum:=max(maxsum, sum);
End.
Birinchi siklning ichidagi operatorlar N marta, ikkinchi siklning ichidagi tashqi siklning har bir qadami uchun N martadan ko’p bo’lmagan qadamlar bilan bajariladi. Demak, algoritm ishlashining umumiy vaqti .
Shunday qilib algoritm ishlash vaqti samaradorligi bo’yicha yahshilandi