線性時(shí)間選擇問(wèn)題的教學(xué)探討

陳曉梅　胡春花

摘要：針對(duì)線性時(shí)間選擇問(wèn)題，分別對(duì)一般情況下的算法思路和最壞情況下的算法思路進(jìn)行介紹，結(jié)合教學(xué)過(guò)程和特點(diǎn)，通過(guò)增加遞歸調(diào)用的結(jié)束條件、無(wú)需改造劃分函數(shù)而直接調(diào)用以及對(duì)相同劃分元素進(jìn)行集中排列等，對(duì)算法進(jìn)行了優(yōu)化和改進(jìn)，增強(qiáng)了算法的連貫性和適用性，使學(xué)生更加直觀深刻地理解和應(yīng)用線性時(shí)間選擇問(wèn)題的算法，收到較好的教學(xué)效果。

關(guān)鍵詞：線性時(shí)間選擇；最壞情況；基準(zhǔn)元素；劃分

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）21-0087-02

1 線性時(shí)間選擇問(wèn)題描述

給定 n 個(gè)元素的集合，集合中的第 k 個(gè)順序統(tǒng)計(jì)量是指集合中的第k 個(gè)（1≤k≤n） 最小元素。當(dāng)k=1時(shí)，指集合中的最小元素；當(dāng)k=n時(shí)，指集合中的最大元素。如何從給定的集合中找出第 k 個(gè)最小元素，被稱(chēng)為元素選擇問(wèn)題。線性時(shí)間選擇問(wèn)題是指在線性時(shí)間內(nèi)實(shí)現(xiàn)元素選擇。該問(wèn)題在大規(guī)模數(shù)據(jù)檢索和人工智能搜索方面有廣泛的應(yīng)用。同時(shí)該問(wèn)題也是分治算法教學(xué)中的一個(gè)典型例子。

2 實(shí)現(xiàn)線性時(shí)間選擇的典型分治算法

2.1 一般性選擇問(wèn)題的分治算法

對(duì)于一般的選擇問(wèn)題，可使用RandomizedSelect（a，p，r，k）實(shí)現(xiàn)在期望情況下對(duì)數(shù)組a[p：r]在線性時(shí)間內(nèi)選出第k小的元素。教材中的函數(shù)描述如下：

RandomizedSelect（）函數(shù)中引入隨機(jī)劃分函數(shù)RandomizedPartition（p，r）對(duì)數(shù)組a[p：r]進(jìn)行劃分，該函數(shù)以a[p：r]中的一個(gè)隨機(jī)元素作為劃分基準(zhǔn)，將原數(shù)組劃分為兩個(gè)子數(shù)組a[p：i]和a[i+1：r]，使得第一個(gè)子數(shù)組中的所有元素全小于等于第二個(gè)子數(shù)組中的所有元素。通過(guò)RandomizedPartition（）函數(shù)的返回值i可以計(jì)算出第一個(gè)子數(shù)組的元素個(gè)數(shù)j，根據(jù)j值與k值的大小比較，可以判斷出所要求的第k小的元素是落在哪個(gè)子數(shù)組，從而繼續(xù)遞歸調(diào)用RandomizedSelect（）函數(shù)對(duì)縮小了查找范圍的子數(shù)組進(jìn)行查找。直至待查找數(shù)組只有一個(gè)元素，則該元素就是要查找的a[p：r]中第k小的數(shù)。

該算法的平均性能很好，可以在O（n）時(shí)間內(nèi)找出結(jié)果。但是，如果每次產(chǎn)生的劃分基準(zhǔn)都是數(shù)組中的最大值或最小值，則算法在這種最壞情況下可導(dǎo)致O（n2）的時(shí)間效率。

2.2 最壞情況下的選擇問(wèn)題的分治算法

對(duì)于每次劃分，如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，以這個(gè)劃分基準(zhǔn)所劃分出的兩個(gè)子數(shù)組的長(zhǎng)度都至少是原數(shù)組長(zhǎng)度的常數(shù)倍（0<<1），那么就可以在任何實(shí)例的情況下都能避免前述最壞情況的發(fā)生，保證了算法一定能在線性時(shí)間內(nèi)找到結(jié)果。函數(shù)Select（）按照這個(gè)思路實(shí)現(xiàn)線性時(shí)間選擇。

Select（）函數(shù)中，將數(shù)組a[p：r]分成?n/5?個(gè)組，每組5個(gè)元素，最后一個(gè)組可能不足5個(gè)元素。對(duì)每個(gè)組分別排序，并取其中位數(shù)，共有?n/5?個(gè)中位數(shù)。調(diào)用Select（）函數(shù)求這?n/5?個(gè)中位數(shù)的中位數(shù)x。以x作為劃分基準(zhǔn)對(duì)a[p：r]進(jìn)行劃分，通過(guò)Partition（）函數(shù)的返回值i可以計(jì)算出劃分后的第一個(gè)子數(shù)組的元素個(gè)數(shù)j，根據(jù)j值與k值的大小比較，可以判斷出所要求的第k小的數(shù)是落在哪個(gè)子數(shù)組，從而繼續(xù)遞歸調(diào)用Select（）函數(shù)對(duì)縮小了查找范圍的子數(shù)組進(jìn)行查找。直至待查找數(shù)組的數(shù)據(jù)量小于75，則直接對(duì)其排序，并返回第k小的元素。

若待查找的數(shù)據(jù)量小于75，則Select（）函數(shù)用于排序的時(shí)間為常數(shù)C。若數(shù)據(jù)量大于75，設(shè)Select（）函數(shù)共需要T（n）時(shí)間，則查找中位數(shù)的中位數(shù)x需要T（n/5）時(shí)間，由于以x作為劃分基準(zhǔn)所得到的兩個(gè)子數(shù)組都不超過(guò)3n/4個(gè)元素，故遞歸調(diào)用Select（）函數(shù)繼續(xù)查找的時(shí)間至多為T(mén)（3n/4）時(shí)間。因此T（n）=O（n）。

3 教學(xué)內(nèi)容探討

可對(duì)2.1中的RandomizedSelect（）函數(shù)和2.2中的Select（）函數(shù)進(jìn)行改進(jìn)，以優(yōu)化算法和有利于學(xué)生更為深入連貫地學(xué)習(xí)線性時(shí)間選擇問(wèn)題。

（1）在計(jì)算j值后判斷相應(yīng)劃分點(diǎn)是否就是所求的第k小元素

RandomizedSelect（）和Select（）函數(shù)中，對(duì)a[p：r]進(jìn)行劃分后，都要計(jì)算劃分點(diǎn)a[i]是數(shù)組的第幾小，計(jì)算結(jié)果為j。函數(shù)中可以插入語(yǔ)句，比較j值與k值是否相等，若相等，則說(shuō)明劃分點(diǎn)a[i]就是所要查找的第k小的元素。因此無(wú)需再繼續(xù)進(jìn)入下一輪的遞歸調(diào)用，返回a[i]，程序結(jié)束。

（3）對(duì)Select（）函數(shù)作進(jìn)一步改進(jìn)

以x作為劃分基準(zhǔn)對(duì)a[p：r]進(jìn)行劃分后，可以在線性時(shí)間內(nèi)將與x相等的元素集中排列在一起，并記錄這些元素的起始下標(biāo)i1和結(jié)束下標(biāo)i2，若i1-p+1≤k≤i2-p+1，則說(shuō)明x就是所要查找的第k小的元素。因此無(wú)需再繼續(xù)進(jìn)入下一輪的遞歸調(diào)用，返回x，程序結(jié)束。否則，進(jìn)一步縮小查找范圍，遞歸調(diào)用Select（）函數(shù)進(jìn)行查找。

4 結(jié)語(yǔ)

如何在最壞情況下實(shí)現(xiàn)線性時(shí)間選擇是分治算法里相對(duì)較難理解的問(wèn)題。本文先介紹一般情況下線性時(shí)間選擇的算法思路，再介紹最壞情況下線性時(shí)間選擇的算法思路。文中針對(duì)教材所提出的算法，分別從算法優(yōu)化方面和算法適用性方面進(jìn)行了改進(jìn)，從而讓學(xué)生能夠更加直觀深刻地理解和應(yīng)用線性時(shí)間選擇問(wèn)題的算法，收到了更好的教學(xué)效果。

參考文獻(xiàn)：

[1] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社， 2012.

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

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