关于BFPRT分治选择算法的最佳性

On the Optimization of BFPRT Selecting Algorithm Based on Divide and Conquer

对基于分治思想设计的ＢＦＰＲＴ选择算法给出了几乎最佳改进，并指出在比较算法类中，基于建立中值序列选中位元素的分治思想，对此算法的任何改进其复杂度至少为８ｎ，其中ｎ为选择问题的大小。

The nearly optimum improved BFPRT algorithm used in solving selecting problem and based ondivide and conquer is presented in this paper,the result is that in comparison algorithm class,forany improved BFPRT algorithm based on constructing median sequence and selecting its median thealgorithm complexitg is at least 8n.