Algoritmlarning samaradorligi va ularning tahlili

Samaradorlikka doir misollar .

Algoritmlar vaqt va qiyinchiliklar fazosi bo’yicha klassifikasiya qilish mumkin. U holda 4-rasmda ko’rsatilgandek, bir nechta shunday algoritmlarni ajratish mumkin. Masalan, agar barcha sondagi elementlatlar uchun, algoritm ishlash vaqti o’zgarmasa, bunday algoritmni o’zgarmas algoritm deyiladi. U kvadratik deyiladi, agar uni bajarish vaqti O(n²) bo’lsa.Quyidagi 4-rasmda har bir sinf uchun bir nechta amallarni bajarish uchun ketgan real vaqti sekundiga 1 million operasiya bajarish yoki mikrosekundiga 1 ta operasiya bajarish xolatida keltirilgan.

4-rasm. Algoritm sinflari va ularni kompyuterda bajarish vaqtlari

(Kompyuter tezligi 1000000amal/sek).

Assimptotic funksiyani aniqlashni misollarda ko’rib chiqamiz.

Assimptotik funksiyalar algoritm samaradorligini baholash uchun ishlatiladi. Bunda asosiy mezon sifatida masalani echish uchun ketadigan vaqt va zarur bo’lgan hotira hajmi hisoblanadi. Endi biz bir nechta misollarda assiptotik funcsiyalarini aniqlashni ko’rib chiqamiz.

Sodda sikl yordamida massiv elementlari yig’indisini hisoblashdan boshlaymiz.

for (i = sum = 0; i < n; i++)
sum += a[i];
Avval 2 ta o’zgaruvchini inisializatsiya qilamiz, sikl n ta iteratsiyadan iborat bo’lib, har bir qadamda yig’indi qiymati sum va i ni qiymati yangilanadi. Demak, algoritm vazifani to’liq echish uchun 2+2n marta amallar bajarishi kerak bo’ladi, ya’ni bu holda assimptotik funksiya O(n) bo’ladi.

Agar ichma-ich joylashgan sikllar bo’lsa assimptotik funksiya darajasi ham ortib boradi. Buni quyidagi barcha nul holatdan boshlanuvchi massiv ostilarini yig’indisini hisoblash misolida ko’rish mumkin. Uning kodi:

for (i = 0; i < n; i++) {
for (j = 1, sum = a[0]; j <= i; j++)
sum += a[j];
cout<<”sum for subarray 0 through “<< i <<” is “<}
Sikl i ni initsializatsiya qilishdan boshlanadi, demak tashqi sikl n marta ishlaydi, va har bir ishlaganda ichki sikldagi 2 ta amal i marta, 3ta amal n marta takroran bajariladi. U holda bajarilgan amallar soni 1+3n + ∑2i=1+3n+n(n-1)=O(n)+ O(n²) = O(n²) kabi bo’ladi. Demak, masalani hal qilish uchun O(n2) tartibdagi sonda amallar bajarilishi kerak.

Ma’lumki ichma-ich joylashgan sikllarda algoritm amallari soni ortib boradi. Lekin bu degani barcha shunday sikllar uchun assimptotik finksiya yuqori tartibli bo’ladi degani emas. Masalan, biz qism massivlarning ohirgi 5 elementlari yig’indisini chop etishga chiqarishni (nolinchi holatdan boshlab) talab qilishimiz mumkin. U holda yuqoridagi kodning tashqi siklini o’zgartirib olishimiz mumkin:

for (i = 4; i < n; i++) {
for (j = i-3, sum = a[i-4]; j <= i; j++)
sum += a[j];
cout<<”sum for subarray “<}

Oddiy hisoblashlarni amalga oshirib bu algoritm samaradorligi

1+8(n-4)+3(n-4)=1+11(n-4)=O(n)

ga teng ekanligini hosil qilamiz. Yuqoridagi misollarda samaradorlikni analiz qilish nisbatan oson, chunki unda sikl chegaralari o’zgarmasdir va ular massivni tartiblanmaganligiga bog’liq emas. Assimptotik funksiyani aniqlash iterasiyalar soni o’zgaruvchan bo’lganda qiyinlashadi. Bu holat quyidagicha misolda ko’rinishi mumkin.

Elementlari o’sish tartibida joylashgan eng uzun qism massivning uzunligini aniqlash kerak bo’lsin. Masalan, [1 8 1 2 5 0 11 12] massivda tartiblangan elementlardan iborat eng uzun qism massiv [1 2 5] bo’lib, uning uzunligi 3 ga teng. Eng uzun osuvchi qism massivni aniqlash kodi quyidagicha bo’ladi:

for(i=0,length=1; i

for(i1=i2=k =i;k< n-1&&a[k]

if(length

length =i2-i1 +1;

}

Agar massiv elementlari kamayuvchi bo’lsa, tashqi sikl n-1 marta ishlaydi, xar bir tashqi sikl iterasiyasida ichki sikl 1 marta bajariladi. Demak, bu holda samaradorlik O(n) bo’ladi. Agar elementlar o’suvchi tartibda joylashgan bo’lsa bu algoritm past samara beradi. Chunki bu holda tashqi sikl n-1 marta bajariladi, ichki sikl esa n-1-i xar bir I 0,1,… n-2 uchun . demak, bu xolda algoritm samaradorligi O(n²) bo’ladi.

Lekin ko’pincha elementlar tartiblangan bo’lmaydi, shuning uchun algoritm samarali bo’ladi. Ohirgi 5-misolda samaradorlikni aniqlashda binar qidiruvdan foydalaniladi. Bizga ma’lumki, binar qidiruvni tartiblangan massivlar uchungina qo’llash mumkin. Bu algoritm quyidagi kod yordamida amalga oshirilishi mumkin:

template //overloaded operator

int binarySearch(constTarr[], int arrSize, const T& key) {

int lo= 0, mid, hi=arrSize-1;

while (lo<= hi) {

mid= (lo+hi)/2; if(key

hi=mid-1;

else if (arr[mid]

lo=mid+1;

else return mid;

//success: return the index of

}  // the cell occupied by key;

return -1; // failure: key is not in the array;

}