Reja: Samaradorlik ko’rsatkichlari

Бахолаш функциялар классификацияси.

Berilgan ikkita f va g funksiyalar uchun quyidagi ta’rifni keltiramiz:

1-ta’rif. f(n) funksiya 0(g(n)) bo’ladi deyiladi, agar shunday musbat c va N sonlar mavjud bo’lsaki , barcha n>=N lar uchun f(n)<=c g(n) tengsizlik bajarilsa.

Bu ta’rifga asosan agar f(n) funksiya 0(g(n)) bo’lsa, u holda uning o’sish tartibi yetarli katta n lar uchun albatta cg(n) funksiya o’sish tartibidan kichik yoki teng bo’lar ekan. Demak, bu holda f(n) funksiya katta n larda cg(n) funksiyadan tez o’sa olmaydi. Bu yerda c va N sonlarini aniqlash muammo bo’lib qoladi, chunki ta’rifda ularni aniqlashning konkret yoli korsatilmagan. Ikkinchidan, bu sonlarga hech qanday shartlar qo’yilmagan. Shuning uchun ularning qiymatlari juda ko’p bo’lishi mumkin.

f(n)=2n^2+ 3n+1=O(n^2) (2)

U holda g(n)=n^2 funksiyani tarifdagi funksiya sifatida oluvchi funksiyalardan biri deb xisoblash mumkin. Ta’rifga asosan, c va N lar uchun quyidagi rasmdagi sonlar juftliklarini olish mumkin bo’ladi. (2) funksiya uchun c va N larning qiymatlari.

N va c ning bunday qiymatlarini quyidagi tengsizlikni yechish orqali aniqlanadi:

2n^2+3n+1<=cn^2; (3)

Undan tashqari n ning darajalari bo’yicha ham assimptotik funksiyalarni juda ko’pini olish mumkin. Bu holda eng kichik tartiblisi tanlab olinadi. Bunday noaniqliklarni xal qilish berilgan funksiyadagi kichik tartibli xadlarni barchasini tashlab yuborish va quyidagicha belgilash orqali amalga oshiriladi. Masalan, (1) funksiya uchun

f(n)=n^2+100n+O(log10n)

ko’rinishda olish , (2) funksiya uchun esa f(n)=2n^2+O(n) kabi ko’rinishda olish mumkin bo’ladi.

O- katta funksiyalarning xossalari:

• 
  Tranzitivlik. Agar f(n) funksiya O(h(n)) bo’lsa, u holda сf(n) funksiya O(h(n)) bo’ladi.
  
• 
  Agar f(n) va g(n) funksiyalarning xar biri O(h(n)) bo’lsa, u holda ularning yig’infisi f(n)+g(n) ham O(h(n)) bo’ladi.
  
• 
  f=an^k funksiya O(n^k) bo’ladi.
  
• 
  f=n^k funksiya ixtiyoriy j>=0 uchun O(n^k+j) bo’ladi.
  
• 
  Agar f(n)=Cg(n) bo’lsa, u holda f(n) funksiya O(g(n)) bo’ladi. Ihtiyoriy a teng emas 1, b teng emas 1 sonlar uchun log(an) funksiya O(log(bn)) bo’ladi.
  
• 
  O- notasiya yordamida funksiyani yuqoridan assimptotik baxolashni ko’rdik. Xuddi shunday baxolashni quyidan ham berish mumkin. Bunday baholashni sigma(Ω) baholash deyiladi va u quyidagicha aniqlanadi:
  
• 
  2- ta’rif. f(n) funksiya Ω(g(n)) deyiladi, agar shunday musbat c va N lar mavjud bo’lsaki , barcha n>=N lar uchun f(n)>=cg(n) tengsizlik o’rinli bo’lsa.
  
• 
  Bu ta’rif ham birinchi ta’rifga juda o’xshash, faqat bu yerda tengsizlik teskaridir.
  
• 
  Yuqoridagi ikkita ta’rifdan foydalanib quyidagio ta’rifni keltirish mumkin.
  
• 
  Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:
  

3-ta’rif. f(n) funksiya Θ(g(n)) deyiladi, agar shunday musbat c1, c2 va N sonlar mavjud bo’lsaki, ular uchun barcha n>=N larda quyidagi tengsizlik o’rinli bo’lsa: c1*g(n)<=f(n)<=c*2g(n).

Endi biz bir nechta misollarda assiptotik funcsiyalarni 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 yechish 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^2) = O(n^2) kabi bo’ladi. Demak, masalani hal qilish uchun O(n^2) tartibdagi sonda amallar bajarilishi kerak.

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^2) bo’ladi

Eng yahshi, o’rtacha va eng yomon algoritmlar.

Yuqoridagi misollarga asoslanib shuni aytish mumkinki, algoritmlar samaradorligi bo’yicha 3 hil bolishi mumrin: 1) Eng yomon holat bunda algoritm masalani echish uchun maksimal sondagi amallarni bajarishni talab qiladi; 2) Eng yaxshi holat bunda algoritm masalani echish uchun minimal sondagi amallarni bajarishni talab qiladi; 3) Ortacha holat bunda algoritm masalani echish uchun maksimal va minimal sonlar orasidagi sondagi amallarni bajarishni talab qiladi.

Sodda hollarda ortacha samaradorlikni aniqlash algoritmga mumkin bolgan kirishlar, har bir kirish uchun algoritm asosida bajarilayotgan etaplar sonini aniqlash, barcha kirishlar uchun qadamlar sonini aniqlash va ularning hammasini qoshib hisoblangandan song kirishlar soniga bolish yordamida amalda oshiriladi.