摘要
对n个元素组成的无序数组，从中找出第k个小的元素的问题，线性时间选择算法的划分基准对算法的时间复杂性起着关键的作用。分别以随机选取数组中一个元素作为划分基准和改进方法--以中间值元素的中间值作为划分基准，对线性时间选择算法进行详细的分析，并推导出相应的时间复杂性。
For the problem of finding the k-th smallest elements from a disorder array with n elements, the dMsion datum of the linear time selection algorithm plays key role to the time complexity of the algorithm. The paper analyzes the two eases ： taking a random element of the array as the division datum and improvement method taking the median value of the median element as the division datum. The time complexities of the two cases are derived.
出处
《计算机与现代化》
2010年第12期27-29,共3页
Computer and Modernization
