1.2　并行算法评价

评价和分析并行算法，主要应关注它的计算复杂性，即算法的运行时间（时间复杂性）与所提供的处理机台数（空间复杂性），并行处理的基本思想是用增加处理机台数来换取时间的节省，为了评价并行算法引入加速比和效率的概念。

对于由P台处理机组成的并行系统，假定每台处理机的算术运算的操作时间相同，设T1为串行算法在单处理机上运行时间，TP为并行算法在P台处理机的系统上的运行时间，则一个并行算法的加速比定义为：

该算法的效率定义为：

加速比和效率是评价并计算法的重要指标，研究并行算法的目标是达到尽可能大的加速比SP=P，理想上，这时并行效率达到EP=1，但一般不可能达到理想的加速比SP=P。