В идеальном случае оценки эффективности для оценки сложности параллельного алгоритма Прима для нахождения минимального охватывающего дерева вычисляются по следующим формулам:
В ходе вычислений в зависимости от количества выбранных вершин вычислительная нагрузка на процессоры может различаться.
Для уточнения полученных показателей эффективности оценим более точно количество выполненных операций и затраты на передачу данных между процессами.
На каждом шаге параллельный алгоритм выбирает вершину с минимальным расстоянием до строящегося дерева и корректирует веса di для каждой вершины. Количество операций при каждой из этих процедур ограничено числом . Поэтому на выполнение n итераций алгоритм затратит следующее время ( r - время на выполнение элементарной операции ):
Сборка данных на одном процессоре может быть выполнена за итераций.
Следовательно, на передачу данных от всех процессоров системы корневому будет затрачено время:
где a - латентность сети передачи данных, B - пропускная способность сети, w - размер одного элемента данных в байтах.
Операция рассылки одного элемента данных требует операций и может быть выполнена за время
Тогда суммарное время работы алгоритма может быть представлено соотношением:
Это выражение показывает, что при больших n время работы параллельного алгоритма будет определяться квадратичной частью выражения и ускорение будет близко к идеальному. При малых же n ускорение будет определятся линейной частью выражения и значение ускорения будет низким.
