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