知识卡片
随机并行加速比取期望时间之比
原书问题26-6(b)提出以 E[T₁]/E[Tₚ] 而非 E[T₁/Tₚ] 定义随机算法加速比,要求读者论证。
按题设:1% 时 T₁=10⁴、T₁₀₀₀₀=1;其余99% 时两者均为10⁹。
前者约1,后者100.99;罕见的极高逐次加速会放大后者。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
b. Consider a randomized parallel algorithm for which 1% of the time, T1 = 104 and T10,000 = 1, but for the remaining 99% of the time, T1 = T10,000 = 109. Argue that the speedup of a randomized parallel algorithm should be defined as E[T1]/E[TP], rather than E[T1/TP].
参考来源
- 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[90000,95000))。
- 结论依据:问题26-6(b)的待证命题及题中两种运行情形;数值比较是依题设自行推导,原书没有在此给出证明。E[T₁]=990000100,E[T₁₀₀₀₀]=990000000.01,所以 E[T₁]/E[T₁₀₀₀₀]≈1.000000101;E[T₁/T₁₀₀₀₀]=100.99。
- 原始内容:b. Consider a randomized parallel algorithm for which 1% of the time, T 1 = 10 4 and T 10,000 = 1, but for the remaining 99% of the time, T 1 = T 10,000 = 10 9 . Argue that the speedup of a randomized parallel algorithm should be defined as E [ T 1 ]/ E [ T P ], rather than E [ T 1 / T P ].