王修君，高 艷，鄭 嘯

(安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243002)

?

算法設(shè)計(jì)和分析的教學(xué)探索

王修君，高 艷，鄭 嘯

(安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243002)

算法設(shè)計(jì)和分析是計(jì)算機(jī)專業(yè)的一門核心基礎(chǔ)課程。以經(jīng)典快速排序算法平均比較次數(shù)的兩種分析方法作為切入點(diǎn)，多角度分析經(jīng)典問題有助于學(xué)生深刻理解算法本質(zhì)；對(duì)經(jīng)典問題采用不同的分析手段而得到同樣的答案這個(gè)過程，有助于學(xué)生體會(huì)分析手段多樣性和算法分析之美。

算法分析；快速排序算法；平均比較次數(shù)分析

算法設(shè)計(jì)與分析課程是計(jì)算機(jī)專業(yè)核心課程之一?，F(xiàn)有的算法設(shè)計(jì)與分析課程的教學(xué)過程往往過于強(qiáng)調(diào)經(jīng)典算法：即讓學(xué)生懂得某些經(jīng)典算法的每一步驟細(xì)節(jié)和大概采用了什么樣的算法設(shè)計(jì)策略等，最終目的是讓學(xué)生可以用某種編程語(yǔ)言實(shí)現(xiàn)經(jīng)典算法。

考慮到學(xué)習(xí)是一個(gè)由簡(jiǎn)單到復(fù)雜，再?gòu)膹?fù)雜到簡(jiǎn)單的過程，而理解一個(gè)算法的本質(zhì)特征只有通過對(duì)算法的細(xì)致分析才可以達(dá)到；[1]同時(shí)考慮到在選擇算法解決實(shí)際問題時(shí)，最為重要的是所選算法的性能，[2-3]而掌握算法的性能知識(shí)不能靠死記硬背。因此多角度的算法性能分析在算法課程教學(xué)過程中起著相當(dāng)重要的作用。筆者通過引入一個(gè)經(jīng)典的快速排序算法的性能分析，展現(xiàn)算法性能的多角度分析，以幫助學(xué)生體會(huì)和理解算法的多行偽碼中的本質(zhì)，掌握算法的特性，體會(huì)算法設(shè)計(jì)與分析中的數(shù)學(xué)之美。

一、經(jīng)典快速排序算法的多角度分析

經(jīng)典的快速排序算法[3-5]如下：

算法輸入：n個(gè)元素互異的列表S={x1,…，xn}

算法輸出：排序后的S

Step 1. 如果S中只有0個(gè)或1個(gè)元素，則直接返回；否則繼續(xù)。

Step 2. 隨機(jī)選擇S中的一個(gè)元素xt,t∈{1,2,…，n}作為劃分元素。

Step 3. 將S中除xc外的其他元素與xc做比較，并劃分S-{xc}為如下兩個(gè)子列表S1,S2;a)S1是S中所有比x1小的元素構(gòu)成的列表;b)S1是S中所有比x1大的元素構(gòu)成的列表。

Step 4. 對(duì)S1,S2快速排序。

Step 5. 返回列表S1,x1,S2。

針對(duì)該經(jīng)典的快速排序算法，本文將給出兩種不同的分析方法來分析平均比較次數(shù)。[2,4]。為了表述方便，我們令Cn表示有n個(gè)元素的列表進(jìn)行快速排序算法的平均比較次數(shù)。

二、基于遞推關(guān)系式的快速排序平均比較次數(shù)分析

分析快速排序算法的step1，顯然針對(duì)只含有0個(gè)元素和1個(gè)元素的列表S不需要排序(本身就是有序的)，可得C0=0,C1=0。對(duì)于S中含有兩個(gè)以上元素的情況，分析快速排序算法的step2到step5步，可得如下遞歸式：

(1)

其中：1/n表示快速排序算法在step2中所選擇的數(shù)xc是S中第i小的元素的概率(i∈{1,2,…，n})。因?yàn)閤c為隨機(jī)選擇，所以xc是第 i大元素的概率相等(i∈{1,2,…，n})。

當(dāng)xc是第i大的元素時(shí)，顯然S中除去xc外的元素被分成兩個(gè)子列表S1,S2。由于S1是S中所有比x1小的元素構(gòu)成的列表，S2是S中所有比x1大的元素構(gòu)成的列表，所以S1中含有i-1個(gè)元素，而S2中含有n-i個(gè)元素。此時(shí)顯然對(duì)S的排序問題分解為對(duì)兩個(gè)子列表S1,S2的排序問題。用快速排序?qū)1,S2排序的代價(jià)為Ci-1+Cn-i(快速排序算法中的step4)。 (1)式右邊的最后一項(xiàng)n-1表示step(3)中xc與S中剩下的n-1元素的n-1次比較操作(經(jīng)過n-1次比較操作后，才能得到S1,S2)。由此，得到遞歸式(1)。下面我們考慮如何找出滿足遞歸式(1)的Cn的閉形式解。

對(duì)(1)式兩邊同乘以n，可得：

(2)

基于(2)，我們可以得到：

(3)

將(2)式和(3)式做差，可以得到如下：

Cn/(n+1)-Cn-1/n=4/(n+1)-2/n

(4)

令B=Cn/(n+1)，我們可以得到如下遞歸式：

Bn-Bn-1=4/(n+1)-2/n

(5)

其中B0=0，B1=1。求解出Bn的通項(xiàng)公式也就可以求解出Cn。顯然有如下等式：

(Bn-Bn-1)+(Bn-1-Bn-2)+(Bn-2-Bn-3)+…+(B2-B1)+(B1-B0)=Bn

(6)

將(5)代入(6)，可得Bn的通項(xiàng)公式如下：

(7)

由(7)，可以獲得Cn的通項(xiàng)公式為：

(8)

通過上面的基于遞歸分析方法的講解，即對(duì)(1)～(7)式的每一步講解，使得學(xué)生可以了解經(jīng)典快速排序算法的偽碼中每行代碼的意義及其對(duì)算法性能影響。

三、基于數(shù)學(xué)期望的快速排序平均比較次數(shù)分析

不失一般性，假設(shè)列表S的有序形式為：x1

令隨機(jī)變量Xx,j=1表示xi、xj在經(jīng)典快速排序算法的某次遞歸中發(fā)生了比較，令Xx,j=0表示在經(jīng)典快速排序算法的整個(gè)運(yùn)行過程中xi和xj沒有發(fā)生比較。顯然，n個(gè)元素的快速排序算法的平均比較次數(shù)Cn可以表示如下：

(9)

其中：E[·]表示數(shù)學(xué)期望運(yùn)算。

令LR表示事件：在算法的某次遞歸中所選擇的劃分元素xc滿足xc=xi或xc=xj；令M表示事件：在算法的某次遞歸中所選擇的劃分元素xc滿足xi

下面我們考慮三種情況：

第一種情況：算法的某次遞歸中被選為劃分元素xcxj，顯然此時(shí)對(duì)xi和xj是否在發(fā)生比較沒有影響(選擇的劃分元素仍然將xi和xj分在一個(gè)列表中)。

基于以上三種情況，并考慮到數(shù)值介于xi和xj之間有(j-i-1)個(gè)元素，分別為：Xi+1,…，Xj-1，加上xi和xj后，共有j-i+1個(gè)元素，我們有如下等式：

(10)

綜合(8)式和(9)式，并基于數(shù)學(xué)期望的線性，可得：

(11)

根據(jù)(11)式中的對(duì)稱性，上式可進(jìn)一步化簡(jiǎn)為：

Cn=2[1/n+2/(n-1)+…+(n-2)/3+(n-1)/2]

(12)

通過基于數(shù)學(xué)期望的分析方法講解，即通過(9)～(10)式的每一步分析講解并與 (1)～(7)對(duì)照，學(xué)生可以深入了解經(jīng)典快速排序算法中比較操作的特性及其與算法平均性能的數(shù)學(xué)關(guān)系。兩種不同的分析方法對(duì)照和相同的分析結(jié)果可以進(jìn)一步加深的學(xué)生對(duì)經(jīng)典快速排序算法的偽碼本質(zhì)的了解，深刻體會(huì)分析方法的多樣性與算法分析之美。

四、兩種分析方法的教學(xué)意義

兩種分析方法得到同樣的結(jié)果：(12)式等價(jià)于(8)式?；谶f推關(guān)系的分析方法，類似數(shù)學(xué)分析中的微分方程，利用的是經(jīng)典快速排序算法中的遞歸機(jī)制，從小規(guī)模問題的解，去發(fā)現(xiàn)通向的解?；跀?shù)學(xué)期望的分析方法，直接求解有n個(gè)元素的快速排序算法的平均比較次數(shù)。該分析方法將數(shù)序期望的線性性和排序問題比較次數(shù)和的線性性結(jié)合，直接分析任意兩個(gè)數(shù)進(jìn)行比較操作的概率，以此獲得單個(gè)期望的值，并求解最終的期望和。通過兩種方法的講解，顯然可以給學(xué)生更多更深刻的啟示，可以幫助學(xué)生更加深入地了解經(jīng)典的快速排序算法。進(jìn)一步，在學(xué)生了解和掌握這兩種技術(shù)后，也可以很好地了解和分析其他快速排序的算法，如多路快速排序算法(即選擇多個(gè)劃分元素)，體會(huì)算法分析之美，可以達(dá)到很好的教學(xué)效果。

[1]Ronald L.Graham, Oren Patashnik, Donald E.Knuth.具體數(shù)學(xué)[M].張凡,張明堯,譯.北京:人民郵電出版社,2013.

[2]Robert Sedgewick, Philippe Flajolet.算法分析導(dǎo)論[M].馮舜璽,李學(xué)武,裴偉東,等,譯.北京:機(jī)械工業(yè)出版社, 2006.

[3]Rajeev Motwani, Parbhakar Raghavan.隨機(jī)算法[M].孫廣中,等,譯.北京:高等教育出版社, 2008.

[4]Michael Mitzenmacher, Eli Upfal.概率與計(jì)算[M].史道濟(jì),等，譯.北京:機(jī)械工業(yè)出版社,2007.

[5]Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein.算法導(dǎo)論[M].潘金貴,等,譯.北京：機(jī)械工業(yè)出版社, 2006.

(責(zé)任編輯 汪繼友)

Teaching Exploration of Algorithm Design and Analysis

WANG Xiu-jun, GAO Yan, ZHENG Xiao

(School of Computer Science and Technology, Anhui University of Technology, Ma’anshan 243002, Anhui, China)

Algorithm design and analysis is the core course of computer science major. Taking the two analytical ways of average comparison times analysis and classical quick sort as breakthrough point and analyze from various perspectives are good for students to understand the algorithm better. The process of solving classic problems with different analytical methods and getting the same results is of great benefit for them to feel the variety of analytical skills and the beauty of algorithm analysis.

algorithm analysis, quick sort, average comparison times analysis

2015-07-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(61402008)；安徽省自然科學(xué)基金資助項(xiàng)目(1408085QF128)

王修君(1983-)，男，安徽樅陽(yáng)人，安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師，博士。

G642

A

1671-9247(2015)06-0085-02