一个选择算法及其并行化

An Algorithm for Selection and Its Parallelization

文中用合并选择的思想及堆上的最佳算法，给出了求解选择问题的一个新算法及其相应的并行化。将串行合并选择算法的复杂度ｎＬｏｇｋ＋Ｏ（ｎ）降低到（ｎＬｏｇｋ）／２＋（ｎＬｏｇＬｏｇｋ）／２＋Ｏ（ｎ），并保持了原并行算法的结构，在ＳＩＭＤ树型机器的并行计算模型上，并行运行时间也有相应的改善，其中ｎ为问题的大小，ｋ为所找元素的序号。

new algorithm and its parallelization for selection is presented in this paper by using mergeselect and optimum algorithms in heap .The complexity of mergese nLogk+O(n) is reduced to nLogk+ nLogLogk+ O(n).New parallel algorithm keeps the old perallel structure.In SLAM tree machine models, its running the is better than that of old aleorithm. There n is the size of the Problem and k is the ordinal number of the element which should be selected.