一个选择算法及其并行化

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

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.