《數據結構》課程中算法分析部分教學探討

李峰

數據結構課程在計算機專業課中屬于難度較大的課程，再加上高職學生的高等數學課程教學內容簡單，離散數學也沒有開設，導致學習效果很差。學生主要反映內容抽象難懂，理論概念難于理解。筆者經過多年的教學總結出了一些心得體會，下面以算法分析部分為例，談談教學內容的組織，希望起到拋磚引玉的作用。

一、算法分析部分的傳統教學

算法分析在數據結構課程中主要是計算算法時間復雜度，也就是算法耗費的時間。這一部分因為設計到數學知識，學生尤其不易掌握。

傳統的教學步驟是，先給出時間復雜度的計算規則，然后使用數學公式進行推導。學生看到這些得出的數學式子，也是沒有實際的概念。一般將問題規模n取值從小到大，以說明為什么考慮“當n充分大時”的時間耗費。如圖1所示。

二、從實驗到理論的逆向教學法

1重視實踐教學

對于高職高專學生來說，具體的數值比抽象的n更容易接受。為了更好的理解和認識算法的效率，我們首先讓學生上機實驗，通過實驗得出的數據來理解關于問題規模n的概念。

比如，采用判斷素數的實驗，實驗要求學生在程序中增加一個計數器以統計關鍵語句的重復次數。實驗輸出的結果更直觀，這就有了通俗直白的理解基礎。

2 精選實驗內容

我們還精心選擇實驗內容，這部分的實驗內容要具備兩點：一是要簡單，代碼只有十來行，算法思路也直觀;二是大家熟悉的問題求解，易于理解。一方面對算法的效率有直觀的認識，另一方面也體現了求解同一問題采用不同算法的效率差別。

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

三、結論

實驗數據不是用來評價和對比算法的，但它使學生對算法的效率問題有了直觀感受，反過來再理解數學式子，符合理論指導實踐，實踐證明理論的認知規律。事實證明，學生對此有良好的反映，教師在不斷的探索教學中收獲了認同。