合并选择算法及其并行化

Mergeselect Algorithm and Its Parallelization

本文基于EMRGESORT算法的思想设计出求顺序统计问题的合并选择算法,串行算法的最坏时间复杂度为θ(nlogk),其中n为问题的大小,k为所找元素的序号。在串行算法之后,在SIMD的树型机器上又给出了算法并行化,并行算法的运实时间为θ(klogn),处理器的总数目为2(n/k)-1。

Based on the mergesort, an algorithm mergeselect for order statisticsis presented in this paper.The time complexity of worst-case of sequentialmergeselect is θ(nlogk), in which n is the size of the problem and k is theordinal number of the element which should be selected. And then theperallelization of sequential mergeselect is given, the parallel computer isa tree machine in SIMD models. The running time of the parallel algorithmis θ(klogn) and the number of processors is 2 (n/k) -1.