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

5-misol. Endi "pufaksimon tartiblash" algoritmi deb nomlangan yana bir algoritmni ko'rib chiqamiz. Uning mohiyati shundan iboratki, qo'shni massiv elementlari taqqoslanadi va agar ular joyida bo'lmasa, ular almashtiriladi. Muammo shundaki, barcha juftlarni bitta tekshirib chiqishda massivni tartiblab olmasligimiz mumkin. Aftidan, bu algoritm avvalgisiga qaraganda ancha yaxshi, ammo shoshilmaslik kerak. Keling, "pufaksimon tartiblash" algoritmini baholaymiz:
Eng yaxshi holat Eng yomon holat

1. 
   do
   

{

2. 
   f=false; 1 n
   
3. 
   for(int i=0; i2
   
4. 
   if(A[i]>A[i+1]) n-1 n(n-1)
   

{

5. 
   t=A[i]; 0 n(n-1)
   
6. 
   A[i]=A[i+1]; 0 n(n-1)
   
7. 
   A[i+1]=t; 0 n(n-1)
   
8. 
   f=true; 0 n(n-1)
   
9. 
   }
   
10. 
    }while(f); 1 n
    

“Pufaksimon saralash” algoritmi uchun eng yaxshi baho 2n + 1 ga teng. Eng yomon ko'rsatkich 6n²-4n. Endi biz bir xil masalani yechadigan ushbu ikkita algoritmni taqqoslashimiz mumkin. Pufaksimon usul "yaxshi" ma'lumotlar uchun yaxshiroq ishlaydi, ammo "yomon" ma'lumotlar uchun Tanlash usuli yordamida saralashdan deyarli uch baravar ko'proq vaqt talab etiladi.

Shunday qilib, qaysi saralash algoritmini tanlashingiz algoritmingiz uchun qanday ma'lumotni kutayotganingizga bog'liq. Agar massivlar saralanishi yoki deyarli saralanishi kutilayotgan bo'lsa, u holda “Pufaksimon saralash” uslubiga ustunlik berish kerak. Agar massivlar saralanishi yoki deyarli saralanishi kerak bo'lsa teskari tartibda “tanlash” usulida saralashga ustunlik berish kerak. Shuni ta'kidlash kerakki, har qanday eng tez saralash algoritmlari uchun eng yomon taxmin O (n_­²) dir.