3622
правки
Изменения
→Анализ
При <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>
<tex dpi=145>O(\frac {n\log(n/p)}{p}+p^2\log(p)+n+p)O(\frac {n\log(n/p)}{p})=O(\frac {n\log(n/p)}{p})</tex>.
