SIMD机器上的两个并行选择算法

摘要

本文在ＳＩＭＤ机器上给出了两个并行选择算法，其一为在树模型上基于归并排序与选中元思想而设计的并行归并选择算法，其二为在共享存贮的机器上基于基数排序的思想而设计的并行基数选择算法，它们的运行时间依次为０（ｋｌｏｇｌｏｎ＋ｎ／ｌｏｇｎ）与０（Ｎ＾ｅ＋ｒｌｏｇｎ）其中０〈ｃ〈１，ｍ为一个记录中的关键字个数，ｒ为基数。