← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3667.a

并行斐波那契有大跨度比

理解等级:中级

把朴素递归 F(n−1) 与 F(n−2) 并行后,工作量仍为 Θ(φⁿ),其中 φ=(1+√5)/2≈1.618;这是因为两棵递归子树仍都要计算。关键路径只经过两棵子树中较慢的一棵,所以跨度满足 T∞(n)=max(T∞(n−1),T∞(n−2))+Θ(1)=Θ(n),并行度为 T₁/T∞=Θ(φⁿ/n)。

并行化并未消除重复计算。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第26章 并行算法 · 查看原书依据

      The parallelism of P-FIB (n) is T1(n)/T∞(n) = Θ(ϕn/n), which grows dramatically as n gets large. Thus, Corollary 26.3 tells us that on even the largest parallel computers, a modest value for n suffices

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[35000,40000))。 - 结论依据:26.1节推导P-FIB的工作量、跨度和并行度。 - 原始内容:The parallelism of P-F IB ( n ) is T 1 ( n )/ T ∞ ( n ) = Θ( ϕ n / n ), which grows dramatically as n gets large. Thus, Corollary 26.3 tells us that on even the largest parallel computers, a modest value for n suffices