知识卡片
并行斐波那契有大跨度比
把朴素递归 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