线性时间选择问题的教学探讨

陈晓梅　胡春花

摘要：针对线性时间选择问题，分别对一般情况下的算法思路和最坏情况下的算法思路进行介绍，结合教学过程和特点，通过增加递归调用的结束条件、无需改造划分函数而直接调用以及对相同划分元素进行集中排列等，对算法进行了优化和改进，增强了算法的连贯性和适用性，使学生更加直观深刻地理解和应用线性时间选择问题的算法，收到较好的教学效果。

关键词：线性时间选择；最坏情况；基准元素；划分

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）21-0087-02

1 线性时间选择问题描述

给定 n 个元素的集合，集合中的第 k 个顺序统计量是指集合中的第k 个（1≤k≤n） 最小元素。当k=1时，指集合中的最小元素；当k=n时，指集合中的最大元素。如何从给定的集合中找出第 k 个最小元素，被称为元素选择问题。线性时间选择问题是指在线性时间内实现元素选择。该问题在大规模数据检索和人工智能搜索方面有广泛的应用。同时该问题也是分治算法教学中的一个典型例子。

2 实现线性时间选择的典型分治算法

2.1 一般性选择问题的分治算法

对于一般的选择问题，可使用RandomizedSelect（a，p，r，k）实现在期望情况下对数组a[p：r]在线性时间内选出第k小的元素。教材中的函数描述如下：

RandomizedSelect（）函数中引入随机划分函数RandomizedPartition（p，r）对数组a[p：r]进行划分，该函数以a[p：r]中的一个随机元素作为划分基准，将原数组划分为两个子数组a[p：i]和a[i+1：r]，使得第一个子数组中的所有元素全小于等于第二个子数组中的所有元素。通过RandomizedPartition（）函数的返回值i可以计算出第一个子数组的元素个数j，根据j值与k值的大小比较，可以判断出所要求的第k小的元素是落在哪个子数组，从而继续递归调用RandomizedSelect（）函数对缩小了查找范围的子数组进行查找。直至待查找数组只有一个元素，则该元素就是要查找的a[p：r]中第k小的数。

该算法的平均性能很好，可以在O（n）时间内找出结果。但是，如果每次产生的划分基准都是数组中的最大值或最小值，则算法在这种最坏情况下可导致O（n2）的时间效率。

2.2 最坏情况下的选择问题的分治算法

对于每次划分，如果能在线性时间内找到一个划分基准，以这个划分基准所划分出的两个子数组的长度都至少是原数组长度的常数倍（0<<1），那么就可以在任何实例的情况下都能避免前述最坏情况的发生，保证了算法一定能在线性时间内找到结果。函数Select（）按照这个思路实现线性时间选择。

Select（）函数中，将数组a[p：r]分成?n/5?个组，每组5个元素，最后一个组可能不足5个元素。对每个组分别排序，并取其中位数，共有?n/5?个中位数。调用Select（）函数求这?n/5?个中位数的中位数x。以x作为划分基准对a[p：r]进行划分，通过Partition（）函数的返回值i可以计算出划分后的第一个子数组的元素个数j，根据j值与k值的大小比较，可以判断出所要求的第k小的数是落在哪个子数组，从而继续递归调用Select（）函数对缩小了查找范围的子数组进行查找。直至待查找数组的数据量小于75，则直接对其排序，并返回第k小的元素。

若待查找的数据量小于75，则Select（）函数用于排序的时间为常数C。若数据量大于75，设Select（）函数共需要T（n）时间，则查找中位数的中位数x需要T（n/5）时间，由于以x作为划分基准所得到的两个子数组都不超过3n/4个元素，故递归调用Select（）函数继续查找的时间至多为T（3n/4）时间。因此T（n）=O（n）。

3 教学内容探讨

可对2.1中的RandomizedSelect（）函数和2.2中的Select（）函数进行改进，以优化算法和有利于学生更为深入连贯地学习线性时间选择问题。

（1）在计算j值后判断相应划分点是否就是所求的第k小元素

RandomizedSelect（）和Select（）函数中，对a[p：r]进行划分后，都要计算划分点a[i]是数组的第几小，计算结果为j。函数中可以插入语句，比较j值与k值是否相等，若相等，则说明划分点a[i]就是所要查找的第k小的元素。因此无需再继续进入下一轮的递归调用，返回a[i]，程序结束。

（3）对Select（）函数作进一步改进

以x作为划分基准对a[p：r]进行划分后，可以在线性时间内将与x相等的元素集中排列在一起，并记录这些元素的起始下标i1和结束下标i2，若i1-p+1≤k≤i2-p+1，则说明x就是所要查找的第k小的元素。因此无需再继续进入下一轮的递归调用，返回x，程序结束。否则，进一步缩小查找范围，递归调用Select（）函数进行查找。

4 结语

如何在最坏情况下实现线性时间选择是分治算法里相对较难理解的问题。本文先介绍一般情况下线性时间选择的算法思路，再介绍最坏情况下线性时间选择的算法思路。文中针对教材所提出的算法，分别从算法优化方面和算法适用性方面进行了改进，从而让学生能够更加直观深刻地理解和应用线性时间选择问题的算法，收到了更好的教学效果。

参考文献：

[1] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社， 2012.

[2] Thomas H. Cormen， Charles E. Leiserson， Ronald L. Rivest， Clifford Stein.

Introduction to Algorithms [M]. Second edition. MIT Press， 2006.