《數(shù)據(jù)結(jié)構(gòu)》課程中算法分析部分教學(xué)探討

李峰

數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)專業(yè)課中屬于難度較大的課程，再加上高職學(xué)生的高等數(shù)學(xué)課程教學(xué)內(nèi)容簡(jiǎn)單，離散數(shù)學(xué)也沒(méi)有開(kāi)設(shè)，導(dǎo)致學(xué)習(xí)效果很差。學(xué)生主要反映內(nèi)容抽象難懂，理論概念難于理解。筆者經(jīng)過(guò)多年的教學(xué)總結(jié)出了一些心得體會(huì)，下面以算法分析部分為例，談?wù)劷虒W(xué)內(nèi)容的組織，希望起到拋磚引玉的作用。

一、算法分析部分的傳統(tǒng)教學(xué)

算法分析在數(shù)據(jù)結(jié)構(gòu)課程中主要是計(jì)算算法時(shí)間復(fù)雜度，也就是算法耗費(fèi)的時(shí)間。這一部分因?yàn)樵O(shè)計(jì)到數(shù)學(xué)知識(shí)，學(xué)生尤其不易掌握。

傳統(tǒng)的教學(xué)步驟是，先給出時(shí)間復(fù)雜度的計(jì)算規(guī)則，然后使用數(shù)學(xué)公式進(jìn)行推導(dǎo)。學(xué)生看到這些得出的數(shù)學(xué)式子，也是沒(méi)有實(shí)際的概念。一般將問(wèn)題規(guī)模n取值從小到大，以說(shuō)明為什么考慮“當(dāng)n充分大時(shí)”的時(shí)間耗費(fèi)。如圖1所示。

二、從實(shí)驗(yàn)到理論的逆向教學(xué)法

1重視實(shí)踐教學(xué)

對(duì)于高職高專學(xué)生來(lái)說(shuō)，具體的數(shù)值比抽象的n更容易接受。為了更好的理解和認(rèn)識(shí)算法的效率，我們首先讓學(xué)生上機(jī)實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)得出的數(shù)據(jù)來(lái)理解關(guān)于問(wèn)題規(guī)模n的概念。

比如，采用判斷素?cái)?shù)的實(shí)驗(yàn)，實(shí)驗(yàn)要求學(xué)生在程序中增加一個(gè)計(jì)數(shù)器以統(tǒng)計(jì)關(guān)鍵語(yǔ)句的重復(fù)次數(shù)。實(shí)驗(yàn)輸出的結(jié)果更直觀，這就有了通俗直白的理解基礎(chǔ)。

2 精選實(shí)驗(yàn)內(nèi)容

我們還精心選擇實(shí)驗(yàn)內(nèi)容，這部分的實(shí)驗(yàn)內(nèi)容要具備兩點(diǎn)：一是要簡(jiǎn)單，代碼只有十來(lái)行，算法思路也直觀;二是大家熟悉的問(wèn)題求解，易于理解。一方面對(duì)算法的效率有直觀的認(rèn)識(shí)，另一方面也體現(xiàn)了求解同一問(wèn)題采用不同算法的效率差別。

例如，計(jì)算兩個(gè)數(shù)的最大公約數(shù)實(shí)驗(yàn)。先從定義出發(fā)，寫(xiě)出算法，如圖3所示。然后采用輾轉(zhuǎn)相除算法，如圖4所示，使用類似這樣的測(cè)試數(shù)據(jù)（1 000 005，1 000 000），學(xué)生發(fā)現(xiàn)后者只需執(zhí)行2次取模運(yùn)算，而前者需要10次運(yùn)算才能找到最大公約數(shù)。學(xué)生震驚之時(shí)正好告訴他們：這是特殊情況，一般的效率還得進(jìn)行數(shù)學(xué)推導(dǎo)。

三、結(jié)論

實(shí)驗(yàn)數(shù)據(jù)不是用來(lái)評(píng)價(jià)和對(duì)比算法的，但它使學(xué)生對(duì)算法的效率問(wèn)題有了直觀感受，反過(guò)來(lái)再理解數(shù)學(xué)式子，符合理論指導(dǎo)實(shí)踐，實(shí)踐證明理論的認(rèn)知規(guī)律。事實(shí)證明，學(xué)生對(duì)此有良好的反映，教師在不斷的探索教學(xué)中收獲了認(rèn)同。