知识卡片
并行归并跨度为对数平方
较长数组中点保证任一递归分支最多处理原规模的四分之三;每层在较短数组上二分找分割点耗对数时间。
最长依赖链遂为对数平方级,不能只因两个分支并行就断言常数跨度。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
The worst-case span of P-MERGE-AUX can therefore be described by the following recurrence: Because this recurrence falls under case 2 of the master theorem with k = 1, its solution is T∞(n) = Θ(lg 2 n).
参考来源
- 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[75000,80000))。
- 结论依据:较长数组对半分割使递归子问题至多 3n/4;原书公式图 `OEBPS/images/Art_P839.jpg`(式26.7)给出跨度递推,随后由主定理得到 Θ(lg²n)。
- 公式图核读:T∞(n) = T∞(3n/4) + Θ(lg n)。此处取最长依赖链,只计一个递归分支。
- 原始内容:The worst-case span of P-M ERGE -A UX can therefore be described by the following recurrence: Because this recurrence falls under case 2 of the master theorem with k = 1, its solution is T ∞ ( n ) = Θ(lg 2 n ).