В качестве отностительной оценки сложности параллельного
алгоритма используем ускорение
S=T1/Tp
где, Tp - время решения
задачи на p процессорах.
T1 = n*log(n).
Вычислительная сложность (время решения задачи) параллельного
алгоритма быстрой сортировки для p потоков определяется выражением:
Tp = N(2n/p) +
n/p * log(n/p),
где первая часть определяет общую трудоемкость всех операций
выбора ведущего элемента и разделения блоков согласно этому элементу, а вторая –
трудоемкость локальной сортировки блоков на последней итерации алгоритма.
Тогда S = n*log(n) / (N(2n/p) + n/p *
log(n/p)).
