中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 并行算法的复杂性度量 Brent定理 令W(n)是某并行算法A在运行时间T(n)内所执行的运算 量,则A使用p台处理器可在t(n)=O(W(n)/p+T(n)时间 内执行完毕。 W(n)和c(n)密切相关 POW(n)/T(n)时,W(n)和c(n)两者是渐进一致的 对于任意的p,c(n)W(n) 国家高性能计算中心(合肥 2021/2/19国家高性能计算中心（合肥） 10 2021/2/19 并行算法的复杂性度量 ▪ Brent定理 令W(n)是某并行算法A在运行时间T(n)内所执行的运算 量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间 内执行完毕。 ▪ W(n)和c(n)密切相关 ▪ P=O(W(n)/T(n))时，W(n)和c(n)两者是渐进一致的 ▪ 对于任意的p，c(n)›W(n)