“線性時(shí)間選擇算法”教學(xué)探討

張惠艷 陳芳

摘要：基于選擇問(wèn)題的線性時(shí)間要求，本文從算法思想、算法實(shí)現(xiàn)以及算法復(fù)雜度三個(gè)部分對(duì)《算法設(shè)計(jì)與分析》課程中“線性時(shí)間選擇算法”的教學(xué)方法進(jìn)行了探討，用圖形直觀地分析了線性時(shí)間選擇算法的時(shí)間復(fù)雜度的最好情況和最壞情況，便于學(xué)生理解和掌握。

關(guān)鍵詞：線性時(shí)間選擇算法; 二次取中法; 算法復(fù)雜度

中圖分類號(hào)：G642 ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）35-0260-04

Discussion on the Teaching of Linear Time Selection Algorithm

ZHANG Hui-yan， CHEN Fang

（Huaiyin Normal University， Huaian 223300，China）

Abstract： Based on the linear time requirement of the selection problem， this paper discusses the teaching method of "linear time selection algorithm"in the course of algorithm design and analysis from three parts： algorithm idea， algorithm realization and algorithm complexity. It analyzes the best and worst situation of the time complexity of linear time selection algorithm intuitively with graph， which is convenient for students to understand and master.

Key words： linear time selection algorithm; median of medians rule; algorithm complexity

1引言

《算法設(shè)計(jì)與分析》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)居于核心地位的專業(yè)課程，學(xué)生無(wú)論是考研究生還是從事IT方面的工作，掌握好這門課的算法理論和算法思想都是非常重要的。這門課不僅要學(xué)習(xí)基本算法理論，還要用程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)算法，以便學(xué)生更好地理解和掌握算法設(shè)計(jì)的基本方法和技術(shù)，有助于學(xué)生進(jìn)一步學(xué)習(xí)計(jì)算機(jī)技術(shù)，適應(yīng)更廣泛的職業(yè)挑戰(zhàn)。迄今為止，算法學(xué)家們?cè)O(shè)計(jì)了許多基本和經(jīng)典的算法，如何將這些算法傳授給學(xué)生，讓學(xué)生熟練掌握并能運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題，是教授這門學(xué)科的教師所面對(duì)的主要問(wèn)題。

大部分高校選用的教材是陳慧楠《算法設(shè)計(jì)與分析》[1]第二版。教材的算法基本都給出了C++的代碼實(shí)現(xiàn)，便于學(xué)生很好地理解和掌握復(fù)雜抽象的算法設(shè)計(jì)理論。但本課程是一門理論性和實(shí)踐性都很強(qiáng)的課程，為了取得好的教學(xué)效果，很多授課老師都探討了該課的教學(xué)方法[2-8]，提出了自己的教學(xué)建議。本文從教學(xué)與實(shí)踐兩個(gè)環(huán)節(jié)針對(duì)該書的第五章“分治法”中的“線性時(shí)間選擇算法”談?wù)劷虒W(xué)體會(huì)。

線性時(shí)間選擇算法是在若干元素中不用排序方法求出其中第k小的方法，并且要求時(shí)間復(fù)雜度是線性的。文中采用了“二次取中法”并結(jié)合遞歸調(diào)用和快速排序的劃分思想得到了求第k小的線性時(shí)間選擇算法。

2 線性時(shí)間選擇算法的課堂教學(xué)

2.1算法描述

1）將S中元素5個(gè)一組分成n/5份，每份5個(gè)元素，若n不是5的整數(shù)倍，剩余元素在分組時(shí)不予考慮;

2）每5個(gè)一組，分別求出每組中間元素;并通過(guò)交換將所有中間值依次存放在序列的最前端;

3）求序列前端M的中間值m*;

4）以二次中間值m*為主元，進(jìn)行劃分操作;

5）如果左子序列元素個(gè)數(shù)p=k，則k-1為第k小元素;如果左子序列元素個(gè)數(shù)p>k，則在左子表中繼續(xù)搜索，如果左子序列元素個(gè)數(shù)p<k，則在右子表中繼續(xù)搜索k-p小元素。

首先引導(dǎo)學(xué)生如何實(shí)現(xiàn)元素分組并將每組元素的中間值調(diào)到整個(gè)序列的最前端？在不排序的情況下如何求得前端序列的中間值？求得中間值后如何對(duì)序列進(jìn)行劃分？劃分后如何找到要求的第k小元素？然后結(jié)合實(shí)例和C++代碼來(lái)詳細(xì)講解這一算法思想。

2.2算法實(shí)現(xiàn)

程序主要代碼段是select函數(shù)：

int select（int k， int left， int right， int r） ? //k是第幾小數(shù)，left為左下標(biāo)，right為右下標(biāo)，r為多少個(gè)元素一組

{ int n=right-left+1;

if （n <= r） ? //問(wèn)題足夠小，返回下標(biāo)

{ InsertSort（left，right）;

return left+k-1;

}

for （int i=1;i<=n/r; ++i）

{ InsertSort（left + （i - 1）*r，left+i*r-1）;

swap（a[left+i-1]， a[left+（i-1）*r+Ceil（r，2）-1]）; ? ?//將每組元素的中間值集中存放在子表前面

}

int j=select（Ceil（n/r， 2）， left， left+ n/r-1， r）; ? ?//n/r表明一個(gè)分了多少組，二次求中間值，其下標(biāo)為j

swap（a[left]， a[j]）;

j = Partition（left， right）; ? ? ? ? ? ? //用二次取中值對(duì)原序列重新劃分

printfMoM（j）; ? ? ? ? ? ? ? ? ? ?//輸出二次取中值

if （k == j-left + 1）

return j;

else if （k < j-left + 1）

return select（k， left， j-1， r）; ? ? ?//左子表第K個(gè)元素

else

return select（k-（j-left +1）， j+1， right， r）; ? //右子表第k-（j-left+1）小元素

}

select函數(shù)中調(diào)用InsertSort排序函數(shù)，當(dāng)序列規(guī)模不超過(guò)5個(gè)元素時(shí)，可以采用InsertSort排序直接求出第k小元素，并且一次取中值等于二次取中值;如果序列規(guī)模超過(guò)5個(gè)元素，則對(duì)序列循環(huán)調(diào)用InsertSort函數(shù)分組排序，并將每一組的中間值調(diào)到序列的最前端，可直接調(diào)用庫(kù)函數(shù)swap，再遞歸調(diào)用select函數(shù)求二次取中值。這里給相應(yīng)的代碼都加上了注釋，理解起來(lái)更容易;swap函數(shù)中還調(diào)用了Ceil函數(shù)，功能相當(dāng)于上取整，代碼如下：

int Ceil（int x，int y） ? ? ? ? ?//x，y均為整形數(shù)

{ if （x%y==0） return x/y;

else return x/y+1;

}

教材中沒(méi)有給出這個(gè)函數(shù)，可讓學(xué)生自己補(bǔ)充上取整函數(shù);緊接著select函數(shù)遞歸調(diào)用自身，求得前端序列的中間值，并用這個(gè)中間值對(duì)整個(gè)序列進(jìn)行劃分，即調(diào)用Partition函數(shù)。最后根據(jù)劃分的結(jié)果以及k值的大小，用if-else語(yǔ)句來(lái)選擇select函數(shù)，繼續(xù)遞歸調(diào)用，最終得到第k小的值。

2.3算法實(shí)例講解

教材中給了35個(gè)元素的求第7小的實(shí)例，對(duì)這個(gè)實(shí)例的運(yùn)行講解可以很好地讓學(xué)生理解上述一系列提問(wèn)。

步驟1：首先將給定的35個(gè)元素存入全局?jǐn)?shù)組a：

int a[35]={41，76，55，19，59，63，12，47，67，45，26，76，74，33，18，65，86，49，77，35，80，53，19，97，22，52，62，39，60，59，29，72，31，56，91};并在主函數(shù)中通過(guò)賦值語(yǔ)句int j=select（7，0，34，5）調(diào)用select函數(shù)。

步驟2：進(jìn)入select函數(shù)，首先調(diào)用InsertSort排序函數(shù)，代碼如下：

void InsertSort（int left， int right） ? ? //插入排序

{ for （int i=left+1; i<=right;++i） ? //從left+1開始進(jìn)行插入，一直到right結(jié)束

{ int temp= a[i];

int j;

for （j=i-1; j>=left&&temp<a[j];j--）

{ a[j+1]=a[j]; ?}

a[j+1] = temp;

}

}

通過(guò)循環(huán)7次調(diào)用InsertSort排序函數(shù)，即依次調(diào)用InsertSort（0，4），InsertSort（5，9），InsertSort（10，14），InsertSort（15，19），InsertSort（20，24），InsertSort（25，29），InsertSort（30，34），將7組元素按從小到大的順序排序，并通過(guò)swap函數(shù)將每組序列的中間元素依次調(diào)至序列的最前端。此時(shí)可得到序列的最前端元素依次是55，47，33，65，53，59，56這七個(gè)元素。

步驟3：程序執(zhí)行int j=select（Ceil（n/r，2），left，left+n/r-1，r）這條語(yǔ)句遞歸調(diào)用select函數(shù)自身，此處n=35，r=5，Ceil（n/r，2）=Ceil（35/5，2）=4，left=0，left+n/r=7傳遞給實(shí)參right，即運(yùn)行select（4，0，6，5），即在前端序列的7個(gè)元素中找出第4小元素，這是select函數(shù)第一次遞歸調(diào)用自身。

步驟4：第二次進(jìn)入select函數(shù)，因7除以5取整結(jié)果是1，所以只有第一組元素需要再排序，得結(jié)果33，47，53，55，65，通過(guò)swap（a[left]，a[j]）語(yǔ)句將53調(diào)至序列的最前端得前端序列為53，47，33，55，65，59，56，程序執(zhí)行int j =Select（Ceil（n/r，2），left，left+n/r-1，r）; 即第三次遞歸調(diào)用select函數(shù)，求前端序列53，47，33，55，65的中間值，即執(zhí)行select（1，0，0，5），直接返回0，完成此次遞歸調(diào)用。

調(diào)用printfMoM（j）輸出函數(shù)，代碼如下：

void printfMoM（int j）

{ cout << "二次取中值為：" <<a[j]<<endl;

for （int i=0;i<35;++i）

{ cout << a[i] << " ";

if （（i+1）%5==0）

cout << endl;

}

}

輸出結(jié)果“二次取中值為53”，這是第一次求得的“二次取中值”。

步驟5：執(zhí)行j=Partition（left，right）;即調(diào)Partition函數(shù)，此處left=0，right=7，代碼如下：

int Partition（int left， int right） ? //劃分函數(shù)，返回分割點(diǎn)

{

int i = left; ? ?//以最左邊的數(shù)為分割點(diǎn)

int j = right + 1; ?//由于do while先執(zhí)行--j，為了保證最右邊的數(shù)參與比較，所以先加一

do

{ do

{ ++i;

} while （a[i] < a[left]）;

do

{ --j;

} while （a[j] > a[left]）;

if （i < j）

swap（a[i]， a[j]）;

} while （i < j）;

swap（a[left]， a[j]）;

return j;

}

即用53對(duì)前端7個(gè)元素序列進(jìn)行第一次劃分。得到劃分結(jié)果為33，47，53，55，65，59，56。此時(shí)元素53所對(duì)應(yīng)的數(shù)組下標(biāo)為2，即j=2;因?yàn)楹瘮?shù)select（4，0，6，5）是要求前端序列得第4小元素，此時(shí)前端序列只有兩個(gè)元素，j=2<4，所以第4小元素應(yīng)是右端序列的第一小元素。

步驟6：執(zhí)行語(yǔ)句Select（k-（j-left+1），j+1，right，r），即第四次遞歸調(diào)用函數(shù)select（1，3，6，5），此時(shí)left=3，right=6，n=right-left+1=4，4<5，直接對(duì)右端序列55，65，59，56進(jìn)行插入排序，得55，56，59，65，它的第1小元素即為55，運(yùn)行結(jié)果是返回3，即j=3，因a[3]=55，得到第二次“二次取中值”55。

步驟7：執(zhí)行swap（a[left]，a[j]）;將55調(diào)到序列的最前端，執(zhí)行j=Partition（left，right）;此處left=0，right=34，即用55完成對(duì)原始序列的第一次劃分，并printfMoM（j）即輸出二次取中值55。

教材對(duì)二次取中值55如何得到的講解得不夠細(xì)，在得到“二次取中值”55時(shí)，程序已經(jīng)在select（7，0，34，5）函數(shù)中遞歸調(diào)用select函數(shù)3次，分別是select（4，0，6，5），select（1，0，0，5）得第一次“二次取中值”并對(duì)前端序列進(jìn)行劃分，其運(yùn)行結(jié)果如圖1;select（1，3，6，5）得第二次“二次取中值”并對(duì)原始序列的劃分，其運(yùn)行結(jié)果如圖2。圖中的紅色下劃線是后標(biāo)注的，可以清楚地看到“二次取中值”在原序列中的位置。很多同學(xué)此處都理解得不夠透徹，這里給出了詳細(xì)的分析運(yùn)行過(guò)程。

步驟8：因?yàn)閖=17，j-0+1=18>k=7，left=0，故執(zhí)行語(yǔ)句else if（k<j-left+1） return select（k，left，j-1，r）;即第五次調(diào)用函數(shù)select（7，0，16，5）。

步驟9：第五次進(jìn)入select函數(shù)，首先調(diào)用InsertSort排序函數(shù)，此時(shí)共17個(gè)元素，5個(gè)元素一組，只需調(diào)用3次InsertSort函數(shù)，依次是：InsertSort（0，4），InsertSort（5，9），InsertSort（10，14），將3組元素按從小到大的順序排序，并通過(guò)swap函數(shù)將每組序列的中間元素依次調(diào)至序列的最前端。此時(shí)可得到序列的最前端元素依次是45，31，22，直接插入排序得22，31，45，前端序列共3個(gè)元素，求其中間元素，即第2小，遞歸調(diào)用select（2，0，2，5）得到j(luò)=1，第6次調(diào)用select函數(shù)結(jié)束，即第三次二次取中值31。用31對(duì)原序列的前17個(gè)元素進(jìn)行劃分，運(yùn)行結(jié)果如圖3所示。可看到劃分后31的下標(biāo)是7，是前17個(gè)元素的第8小元素，因此第7小元素應(yīng)在31的左端繼續(xù)找。

步驟10：因?yàn)閖=7，j-0+1=8>k=7，left=0，故執(zhí)行語(yǔ)句else if（k<j-left+1） return select（k，left，j-1，r）;即調(diào)用函數(shù)select（7，0，6，5）。

步驟11：第7次進(jìn)入select函數(shù)，執(zhí)行select（7，0，6，5）此時(shí)共7個(gè)元素，18，22，26，19，19，12，29。首先調(diào)用InsertSort排序函數(shù)，5個(gè)元素一組，只需1次調(diào)用InsertSort函數(shù)即InsertSort（0，4），得18，19，19，22，26，取中間值19，第八次調(diào)用select（1，0，0，5），得j=0，第八次遞歸調(diào)用結(jié)束，得到第四次二次取中值19，并通過(guò)swap函數(shù)將19調(diào)至序列的最前端。用19對(duì)這7個(gè)元素進(jìn)行劃分，得18，12，19，22，26，19，29，運(yùn)行結(jié)果如圖4所示。19的下標(biāo)j=2，所以j-left+1=2-0+1=3，此時(shí)k =7>3，因此第7小元素應(yīng)在a[2]=19的右側(cè)，執(zhí)行return select（k-（j-left+1），j+1，right，r），即調(diào)用select（4，3，6，5）。

步驟12：第九次進(jìn)入select函數(shù)，此時(shí)共4個(gè)元素，因此進(jìn)行InsertSort排序，排序結(jié)果是19，22，26，29，調(diào)用結(jié)束返回select函數(shù)，執(zhí)行return left+k-1，3+4-1=6，即返回下標(biāo)6，selcet函數(shù)調(diào)用到此結(jié)束，回到主函數(shù)，j=6即29即為所求得第7小元素，程序到此運(yùn)行結(jié)束。主函數(shù)如下：

int main（）

{

int j=select（7，0，35-1，5）;

cout <<"第七小的值為："<<a[j]<< endl;

return 0;

}

至此教材中選用的35個(gè)元素把selcet函數(shù)的每一條語(yǔ)句都執(zhí)行了一次，主函數(shù)依次調(diào)用了select（7，0，34，5），select（4，0，6，5），select（1，0，0，5），select（1，3，6，5），select（7，0，16，5），select（2，0，2，5），select（7，0，6，5），select（1，0，0，5），select（4，3，6，5），select函數(shù)共被調(diào)用了9次。教材中此例的元素個(gè)數(shù)35和各元素的值以及求解第7小的設(shè)計(jì)都考慮得特別巧妙，這是一個(gè)值得所有學(xué)算法的學(xué)生好好學(xué)習(xí)的實(shí)例，可以很好地幫助學(xué)生理解程序的遞歸調(diào)用，提高學(xué)生的算法理解和實(shí)現(xiàn)能力。

3 線性時(shí)間選擇算法的復(fù)雜度分析

教材中給出了線性時(shí)間選擇算法的復(fù)雜度分析，但不夠直觀，這里結(jié)合圖形給出線性時(shí)間選擇算法的最好和最壞時(shí)間復(fù)雜度分析。n個(gè)元素（元素可重復(fù)），5個(gè)元素為一組，共分為n/5（最后的幾個(gè)元素可不考慮）每組按從小到大的順序排序，如圖5所示：

假設(shè)m*的左側(cè)有r列，右側(cè)有r列，則問(wèn)題的規(guī)模：n=5（2r+1）=10r+5，子問(wèn)題最壞情況：3r+2+2r+2r=7r+2;最好情況：3r+2+2r=5r+2，可以根據(jù)算法步驟分析得到問(wèn)題最壞時(shí)間復(fù)雜度為：T（n）=T（n/5） +T（7/10n）+cn，用遞歸樹易得：T（n）=O（n）;最好時(shí)間復(fù)雜度為：T（n）=T（n/5）+T（1/2n）+cn，用遞歸樹易得：T（n）=O（n）;因此該算法具有線性時(shí)間復(fù)雜度。若3個(gè)元素一組是否能得到線性時(shí)間復(fù)雜度？7個(gè)元素一組呢？留給讀者考慮。

4 結(jié)語(yǔ)

線性時(shí)間選擇算法因?yàn)榻Y(jié)合了元素的排序、劃分以及函數(shù)的遞歸調(diào)用，教師在講解以及學(xué)生在理解接受這一算法的過(guò)程中都有一定的難度，這里結(jié)合本人上課實(shí)際情況以及授課效果給出了一種易懂易掌握的方法，該方法收到了非常明顯的教學(xué)效果，激發(fā)了學(xué)生對(duì)算法學(xué)習(xí)的興趣。

參考文獻(xiàn)：

[1] 王曉東.算法設(shè)計(jì)與分析第二版[M].北京：清華大學(xué)出版社，2016.

[2] 畢方明，楊文嘉.算法與復(fù)雜度分析案例化教學(xué)改革[J].教育教學(xué)論壇，2018（44）：102-103.

[3] 南姣芬， 楊文雅， 李紅嬋，等. 《算法設(shè)計(jì)與分析》教學(xué)過(guò)程中的思考[J]. 教育現(xiàn)代化， 2019，6（35）：195-196.

[4] 袁李萌子， 周杰. 《算法分析與設(shè)計(jì)》課程教學(xué)初探[J]. 教育現(xiàn)代化， 2019，6（70）：89-90..

[5] 郭惠芳，劉寒冰.算法設(shè)計(jì)與分析課程研討教學(xué)的探索[J].計(jì)算機(jī)教育，2018（4）：60-62.

[6] 秦丹.算法設(shè)計(jì)與分析教學(xué)常見問(wèn)題分析[J].電腦知識(shí)與技術(shù)，2014，10（24）：5719-5720.

[7] 季曉慧， 姚國(guó)清， 張玉清，等. 計(jì)算思維與實(shí)踐編程能力培養(yǎng)并重的算法設(shè)計(jì)與分析教學(xué)[J]. 電腦知識(shí)與技術(shù)：學(xué)術(shù)版， 2020，16（4）：70-71.

[8] 范昊，束德勤.《算法設(shè)計(jì)與分析》課程教學(xué)方法研究[J].教育教學(xué)論壇，2020（9）：246-247.

【通聯(lián)編輯：王力】