Изменения

Перейти к: навигация, поиск

Обсуждение:PSRS-сортировка

6 байт добавлено, 22:21, 11 июня 2014
Нет описания правки
|style="background-color:#FFF;padding:2px 10px"| '''20''' 27 32 '''33''' 53 58 '''72''' 84 97
|}
 
 
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
|style="background-color:#FFF;padding:2px 10px"| 33 69
|}
 
 
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
При <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>\displaystyle 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>. В итоге мы получим <tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex><tex dpi=145> =O(\frac {n\log(n/p)}{p}+p^2\log(p)+\frac {n}{p\log p}+p)=O(\frac {n\log(n/p)}{p})</tex>.
=== См. также ===
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
77
правок

Навигация