一个新的顺序统计算法

A new algorithm for order statistics

本文给出了一个新的顺序统计算法 ,证明了在最坏情况下的时间复杂性。当k≤n/ 5时 ,T(n ,k)=n/ 2 +3.0 45 (n +4k) ;当k≥ 4n/ 5时 ,T(n ,k) =n/ 2 +3.0 45 (5n - 4k) ,改进了文献 [1,2 ]中相应结果。

In this paper, we present a new algorithm for order statistics and proved the worst-case complexity. If k≤n/5 then T(n,k)=n/2+3.045(n+4k), if k≥4n/5, then T(n,k)=n/2+3.045(5n-4k) will improve the corresponding results of ,.;