16-ma’ruza. Sodda parallel algoritmlar

Samaradorlik tahlili. 
Shell algoritmining parallel analogining 
samaradorligini baholash uchun parallel pufakchani saralash usuli uchun 
olingan munosabatlardan foydalanish mumkin . Bunday holda, faqat Shell 
algoritmining ikki bosqichli xususiyatini hisobga olish kerak - bu 
xususiyatni hisobga olgan holda, yangi parallel usulning umumiy 
bajarilish vaqtini ifoda yordamida aniqlash mumkin. 
𝑇
𝑝
= (
𝑛
𝑝
) log
2
(𝑛/𝑝)𝜏 + (log
2
𝑝 + 𝐿)[(2𝑛/𝑝)𝜏 + (𝛼 + 𝜔 ∙ (𝑛/𝑝)/𝛽)]
Koʻrib turganingizdek, Shell saralashning parallel versiyasining 
samaradorligi sezilarli darajada L qiymatiga bogʻliq - L ning kichik 
qiymati uchun yangi parallel tartiblash usuli ilgari koʻrib chiqilgan toq-
juft almashtirish algoritmiga qaraganda tezroq. 
 
Takrorlash uchun savol va topshiriqlar: 
1.
Saralash tushunchasiga ta’rif bering 
2.
Yuqorida keltirilgan saralash algoritmlaridan tashqari yana qanday 
saralash algoritmlarini bilasiz? 

---

3.
Shell algoritmining murakkabligini baholang 
4.
Saralash algoritmini parallellashtirishda nimalarga e’tibor berish 
kerak? 
5.
Saralash algoritmlarining samaradorligini tahlil qiling