Для анализа будем использовать следующие показатели:
T1 - время решения задачи на одном процессоре.
Tp - время решения задачи на p процессорах.
S - ускорение (speedup). Ускорение определяется из отношения:
S=T1/Tp
Оценка сложности последовательного алгоритма
T1 = nlogn
Для p потоков:
Tp=(n/p)*log(n/p) + log p + log(n/p)*log p
S = o(nlogn)/o( n/p)*log(n/p) + log p + log(n/p)*log
p)
