2002-北京卷文-20 解-并行计算时间

本题导读

本题考查并行计算的算法设计。核心在于倍增合并减少时间。

📌【题干】

Question

（2002年北京卷(文)） 在研究并行计算的基本算法时，有以下简单模型问题：用计算机求 $n$ 个不同的数 $v_1,v_2,\cdots ,v_n$ 的和 ${\sum }_{i=1}^n{v}_i=v_1+v_2+\cdots +v_n$.计算开始前，$n$ 个数存贮在由网络连接的 $n$ 台计算机中，每台机器存一个数.计算开始后，在一个单位时间内，每台机器至多到一台其他机器中读数据，并与自己原有数据相加得到新的数据，各台机器可同时完成上述工作.

(1) 当 $n=4$ 时，至少需要多少个单位时间可完成计算？

(2) 当 $n=128$ 时，要使所有机器都得到 ${\sum }_{i=1}^n{v}_i$，至少需要多少个单位时间可完成计算？

🔍【思路分析】

破题导航

1. $n=4$ 时两两合并再合并，$2$ 个单位时间。
2. $n=128$ 时倍增合并，$\lceil {\log }_{2}128\rceil =7$。

✅【答案】

Success

(1) $2$ 个单位时间

(2) $7$ 个单位时间

✍【详细解析】

Abstract

(1) 第一单位时间 $1$、$2$ 号机器与 $3$、$4$ 号机器分别两两相加，第二单位时间再合并，故 $n=4$ 时至少 $2$ 个单位时间． (2) 每次单位时间可使”已知部分和”的机器数倍增，$n=128$ 时需 $\lceil {\log }_{2}128\rceil =7$ 个单位时间．

💡【考点归纳与避坑指南】

Danger

核心考点：并行计算时间

核心方法：$n=4$ 时 $2$ 个单位时间；$n=128$ 时 $7$ 个单位时间（倍增求和）

避坑指南：并行计算时间按 $\lceil {\log }_{2}n\rceil$ 估计

📖【试题探源与推广】

Tip

试题探源：源于教材算法与倍增

结论推广：一般地，并行求和时间为 $\lceil {\log }_{2}n\rceil$

方法推广：倍增合并思路

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 22.01 计数原理、排列与组合
• 25.01 程序框图与基本逻辑结构

类题演练 (Links)

• 2005-上海卷文-22 解-新定义分段函数
• 2006-湖南文-20 解-逆序数新定义与放缩
• 2005-北京春文-20 解-折线函数新定义