Chapter 4 划分和分治

数列求和

使用scatter和reduce节约t_startup

主进程:
s=n/p
scatter( numbers,&s,Pgroup,root=master)
reduce_add(&sum,&s,Pgroup,root=master)
从进程:
scatter( numbers,&s,Pgroup,root=master)
……
reduce_add(&part_sum,&s,Pgroup,root=master)

若使用scatter+reduce,通信复杂度为

tcomm = 2* (tstartup + n * tdata)

• tstartup 启动时间，握手时间

否则为

tcomm = 2 * (p * tstartup + n * tdata)

桶排序

有效的前提是均匀分布

自适应积分

错误的情况下可能终止较快

n-天体运行

Barnes-Hut算法

• 整个空间看作一个包含很多物体的立方体。
• 整个空间分为8个子立方体。
• 如果某子立方体不包含物体，则被删除
• 否则保留下来。
• 如果子立方体包含超过一个物体，则递归地划分。直至只包含一个物体为止。

每个物体受到的力只需要从根节点开始遍历树即可：

• 底层立方体内的点，以单个天体的方式计算。
• 上层直至顶层的节点均以立方体的方式计算。

其计算复杂度也为O(nlogn) （每个物体为logn，n个物体）

也即总体复杂度为O(nlogn) ， 优于o（N2）。