Variant №59 Eng yaxshi, oʼrtacha va eng yomon algoritmlar. Matritsaga yangi element qoʼshish algoritmi, misol keltiring. Qoʼyish orqali saralash algoritmlarining tahlili. Javoblar

Xujaqulov Xusniddin

CAL012
Variant № 59

1. 
   Eng yaxshi, oʼrtacha va eng yomon algoritmlar.
   
2. 
   Matritsaga yangi element qoʼshish algoritmi, misol keltiring.
   
3. 
   Qoʼyish orqali saralash algoritmlarining tahlili.
   

Javoblar:

1. Eng yaxshi, oʼrtacha va eng yomon algoritmlar.

Eng yaxshi holat

Boʼlimning nomlanishidan ham koʼrinib turibdiki, algoritmlar uchun eng yaxshi holat bu qisqa vaqt ichida amalga oshiriladigan algoritmning maʼlumotlar jamlanmasi. Bunday jamlanma algoritm eng amal bajaradigan

qiymatlar kombinatsiyasini ifodalaydi. Аgar biz izlash algoritmini tekshirsak, izlangan qiymat birinchi algoritm tekshirayotgan katakka yozilgan boʼlsa (odatda maqsadli qiymat yoki kalit deb ataladi), maʼlumotlar toʼplami eng yaxshi hisoblanadi. Bunday algoritmga uning murakkabligidan qatьiy nazar, bitta taqqoslash kerak boʼladi. Shuni eslatish kerakki, roʼyxatdan izlashda, uning qanchalik uzun boʼlishidan qatьiy nazar, eng yaxshi holat doimiy vaqtni talab qiladi. Umuman, eng yaxshi holatda algoritmni bajarish vaqti kichik yoki doimiy boʼladi, shuning uchun biz bunday tahlilni kam oʼtkazamiz.

Eng yomon holat

Eng yomon holatni tahlil qilish juda muhim, chunki u algoritm ishining maksimal vaqtini tasavvur qilishga yordam beradi. Eng yomon holatni tahlil qilganda algoritm eng koʼp ish bajaradigan kirish maʼlumotlarini topish zarur. Izlovchi algoritm uchun bu kabi kiruvchi maʼlumotlar – bu shunday roʼyxatki, unda izlangan kalit oxirida keladi yoki umuman boʼlmaydi. Natijada N taqqoslash kerak boʼladi. Eng yomon holatning

tahlili tanlangan algoritmga qarab dasturning ishlash vaqti uchun yuqori bahoni beradi.

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

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.