计算复杂性巡回和周相

计算复杂性巡回和周相在上面提到的模型中,有的是串行模型,有的则是并行模型

如前所述,并行模型的串行时间相当于计算过程中的总运算量

至于串行模型的并行时间,可以认为它是一个叫作巡回的量

简而言之,巡回是计算过程中周相的总数

而周相则是计算过程中的一个阶段,在此阶段内写入工作空间的信息不会在同一阶段中读出

由此可见,串行模型的巡回相应于并行模型的并行时间

对于一个问题类而言,存在一个高速并行算法的充要条件是可以找到一个具有小的巡回数的串行算法

以上内容由大学时代综合整理自互联网,实际情况请以官方资料为准。

相关