1-laboratoriya ishi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari. Hisoblash modellari va algoritmlarning murakkabligi. Murakkablikning asosiy resurslari: vaqt, xotira. Oddiy klassik algoritmlarni murakkabligi baholash

4-misol. Ichki sikllarni o'z ichiga olgan yanada murakkab algoritmlarni baholashning misoli sifatida ikkitasini ko'rib chiqamiz.

Masalaning sharti. a1, a2, ..., an butun sonlar qatori berilgan. Massiv tarkibiy qismlarini kamaymaydigan tartibda joylashtiring.

Birinchi algoritm massiv elementlarni tanlash usuli yordamida saralash.
Uning mohiyati quyidagicha. Butun massivda minimal element qidiriladi va birinchi o'ringa qo'yiladi, massivning qolgan qismida minimal qidiriladi va ikkinchi o'ringa qo'yiladi va hokazo, massivning oxirgi elementi ko'rib chiqilmaguncha bu ish davom ettiriladi. Ushbu algoritmdan odamlar kundalik hayotda foydalanadilar. Bu algoritm ancha "yomon", ya'ni samarasiz ko'rinadi. Keling, ushbu algoritmni batafsil ko'rib chiqaylik:

1. 
   for(int i=0; i

{

2. 
   min1=A[i]; n-1
   
3. 
   k=i; n-1
   
4. 
   for(int j=i+1; j2+n-2)/2
   
5. 
   if(min1>A[j]){ (n²-n)/2
   
6. 
   min1=A[j]; 0 dan (n²-n)/2 gacha
   
7. 
   k=j; 0 dan (n²-n)/2 gacha
   
8. 
   }
   
9. 
   A[k]=A[i]; n-1
   
10. 
    A[i]=min1; n-1
    
11. 
    }
    

4-operatorning quyidagicha olinadi. Ushbu sikl sarlavhasi har bir i uchun bajariladi va i = 1 uchun n marta, i = 2 uchun n - 1 marta va hokazo, i = n - 2 - 3 marta, i = n -1 2 marta bajariladi. Ya'ni, bizda a₁, a₂, ..., a_m arifmetik progressiyasi bor, ularning yig'indisi

sm =	(a1	+ am ) ⋅ m
		2

Bu yerda m = n-1, a₁ = n, a_n-1 = 2 va yig'indisi (n + 2) (n-1) / 2 = (n² + n-2) / 2.
5-operatorning bahosi xuddi shu tarzda olinadi, shunchaki unutmang for siklining asosiy qismihar doim tanasiga qaraganda yana bir marta bajariladi. Bu yerda m = n-1, a₁ = n-1, a_n-1 = 1 va yig'indisi .

5- va 6-operatorlarning baholariga kelsak, biz bunga oldinroq duch kelganmiz.

Kiritilgan ma'lumotlarga qarab, ushbu operatorlar boshqacha marta bajarilishi mumkin. "Yaxshi" ma'lumotlar uchun (massiv allaqachon saralangan qilingan), bu operatorlar hech qachon bajarilmaydi. "Yomon" ma'lumotlar uchun ushbu operatorlar har bir tekshirishda min>a[j] bajariladi. Algoritmlarni saralash uchun "yomon" ma'lumotlar teskari tartibda saralangan massivdir.

Shunday qilib, saralash algoritmi uchun eng yaxshi ball n² + 5n-5, eng yomon ko'rsatkich esa 2n²+4n-5. Yomonmi yoki yaxshimi? Hozircha faqat massiv allaqachon saralangan bo’lsa, algoritm ko'p vaqt sarflashini sezishingiz mumkin. Bu ushbu algoritmning aniq kamchiliklaridir.