77
правок
Изменения
Нет описания правки
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex dpi=145>O( \frac {n\log(n/p)}{p})</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>, их сортировать мы будем с помощью [[Быстрая сортировка|быстрой сортировки]], а так же учитывая, что их количество порядка <tex>p</tex>, то можно сказать, что они сортируются за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>.
После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре. Также мы должны помнить, что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин. Поэтому <tex>\mathrm {merge} </tex> займёт <tex dpi=145> O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>. <br>
Откуда получаем итоговую асимптотику:
<tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex> <br> Что равно: <br>
<tex dpi=145>O(\frac {n\log(n/p)}{p}+p^2\log(p)+n+p)=O(\frac {n\log(n/p)}{p})</tex>.
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
* [[Быстрая сортировка|Быстрая сортировка]]
== Источники информации ==* [[wikipedia:ruhttps:Сортировка слиянием//wiki.engr.illinois.edu/download/attachments/99155993/Sort+ParaProg(Quinn)chpt14.5.pdf?version=1&modificationDate=1203641170000|Сортировка слиянием {{---}} Википедия]Статья о PSRS]* [[wikipedia:ruhttp:Быстрая сортировка//users.cms.caltech.edu/~cs284/lectures/29oct97/sld003.htm|Быстрая сортировка {{---}} Википедия]Презентация]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Сортировка]]
