原书出处
Introduction to Algorithms, Fourth Edition
26 第26章 并行算法
RIX-MULTIPLY, the work is the same as the running time of MATRIX-MULTIPLY: T1(n) = Θ(n3).
The span is T∞(n) = Θ(n), because it follows a path down the tree of recursion for the parallel for loop starting in line 1, then down the tree of recursion for the parallel for loop starting in line 2, and then executes all n iterations of the ordinary for loop starting in line 3, resulting in a total span of Θ(lg n) + Θ(lg n) + Θ(n) = Θ(n). Thus the parallelism is Θ(n3)/Θ(n) = Θ(n2).
(Exercise 26.2-3 asks you to parallelize the inner loop to obtain a parallelism of Θ(n3/l
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter026.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea