Two sequences of items sorted in increasing order are given: asequence A of size n and a sequence B of sizem. It is required to determine, for every item of A,the smallest item of B (if one exists) that is larger than it.The paper presents two parallel algorithms for the problem. The firstalgorithm requires O(logm+logn) time using nprocessors on an EREW PRAM. On an EREW PRAM with p(p⩽min{m, n}) processors, the secondalgorithm runs in O(logn+p/n) time whenm⩽n, or in O(logm+p/nlogn/2m) time when mn.The second algorithm is optimal
展开▼
机译：给出了两个按升序排列的项目序列：
大小为 n 的序列 A 和大小为 B 的序列
m 。对于 A 的每个项目，都需要确定
B 的最小项目（如果存在）大于该项目。
本文提出了针对该问题的两种并行算法。首先
算法需要使用 n 的O（log m + log n ）时间
EREW PRAM上的处理器。在具有 p 的EREW PRAM上
（ p ＆les; min { m ， n }）个处理器，第二个
算法在以下情况下以O（log n + p / n ）时间运行
m ＆les; n ，或O（log m + p / n
log n / 2m ）时间，当 m > n 时。
第二种算法是最优的
展开▼
