Mavzu: Asimptotik analizga murojaat usullari. Mummolar & yechimlar

Assimptotik funksiyani aniqlash iterasiyalar soni o’zgaruvchan bo’lganda qiyinlashadi. Bu holat quyidagicha misolda ko’rinishi mumkin.

• 
  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

• 
  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.