知识卡片

普通读书笔记卡 · 3673.a.3

并行归并跨度为对数平方

理解等级:中级

较长数组中点保证任一递归分支最多处理原规模的四分之三;每层在较短数组上二分找分割点耗对数时间。

最长依赖链遂为对数平方级,不能只因两个分支并行就断言常数跨度。

这张卡片看不懂?

已有反馈 · 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 ).