← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

26 第26章 并行算法

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.745Z

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