用Python驗證數據結構與算法的關系

浦丕志 趙春芝

在計算機領域，算法實質上就是針對所處理問題的需要，在數據邏輯結構和存儲結構的基礎上施加的一種運算規則。對問題中的數據的不同組織方式、解決問題的不同的策略將導致不同的算法。在解決實際問題時，要先分析其邏輯關系，建立抽象模型，再選擇合理的數據結構來存儲數據，通過算法解決其核心問題，實現解決問題的過程。

學生在學習實踐中，基本能夠合理選擇數據結構和算法，但對算法的效率關注不多。在教學中，筆者以“求斐波那契數列的第19項的值”一題為例，讓學生體驗不同算法之間效率的差異性。

方法1：用遞歸算法實現求斐波那契數列的第19項的值（如下頁圖1）。

方法2：用遞推算法實現求斐波那契數列的第19項的值（如下頁圖2）。

兩個程序的運行結果相同，但從程序運行時間來看，遞推算法優于遞歸算法。

算法效率

算法效率的高低通常由算法的復雜度來度量。算法復雜度分為時間復雜度和空間復雜度，時間復雜度是指執行算法所需要的計算工作量，而空間復雜度是指執行算法所需要的內存空間。

在學生理解“問題規?！焙汀皶r間復雜度表述”方法后，筆者結合例題“求1+2+…+n的和”，幫助學生學習使用Python程序來驗證數據結構與算法的關系。

方法1：用等差數列公式實現1+2+…+n的求和（如下頁圖3）。

這個程序用等差數列公式直接求解，算法中語句執行次數與問題規模n無關，時間復雜度為O（1）。

方法2：用循環結構實現1+2+…+n的求和（如下頁圖4）。

程序里面用到了循環結構，當問題規模n增大時，循環次數和“s=s+i”的累和過程也線性增大，時間復雜度為O（n）。

從“常量階”和“線性階”的對比來看，算法對問題解決的影響很大，也驗證了研究算法復雜度的價值和意義。

接下來結合例題“求數列的和”“求2n-1的值”“求遞歸數列的值”，即時間復雜度分別為O（n2）、O（ log2n）、O（2n）的算法，幫助學生理解“平方階”“對數階”“指數階”在程序執行時間隨問題規模增長而增長的量級，體驗算法的優勢，具體代碼掃描文末二維碼。

時間復雜度

通過學習，學生很容易理解時間復雜度并不是表示程序真正的執行時間，它表示的是程序執行時間隨數據規模增長的變化趨勢，也是“漸進時間復雜度”，簡稱“時間復雜度”。在此建議教師給學生提供以下程序資源包，供學生驗證使用，程序資源包掃描文末二維碼。

此時可以根據程序資源包，測試一下程序運行時間，從而總結出常見的時間復雜度耗費時間的大小關系：O（1）

空間復雜度

教材中通過問題與討論引導學生通過查閱相關資料，舉例說明空間復雜度如何度量。在教學時，建議教師鼓勵學生開展合作學習，通過資料查閱和討論，匯總學習經驗，實現對“空間復雜度”的學習。指導學生進行學習的步驟可以安排如下。

1.空間復雜度的概念

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度，記作S（n）。

2.空間復雜度量度

計算機在運行程序時，會包含存儲程序空間、輸入和輸出數據占用的存儲空間、程序運行過程中臨時產生的存儲空間三方面的存儲空間。

如果算法占用的臨時存儲單元不受問題規模大小影響，這種算法就是空間復雜度優秀的算法;有的算法占用的臨時存儲空間與問題的規模相關，當問題的規模越來越大時（算法沒干預）需要的存儲空間也越來越大（會溢出），這種算法就需要考慮優化空間復雜度。

3.數據結構所占的空間復雜度

在教學中，建議讓學生測試和討論上面程序，明確字符串類型、一維和多維列表數據類型的空間復雜度。

4.以空間換時間

現在的計算機存儲空間都非常大，通常都可以滿足程序對大數據存儲的需求，因此，在設計算法時，考慮更多的是優化算法的時間復雜度，這就是“空間換時間”。

以“判斷素數”為例，可以先用列表存儲所有問題規模以內的數據，再使用“篩法”將所有為非素數的列表設置為“False”，完成后再“打表”輸出。雖然這種算法在存儲素數數組時占用了大量的空間，但當判斷某個數是不是素數時，效率非常高，時間復雜度為O（1）。

算法與數據結構是問題求解中相輔相成、不可分割的兩個方面。在學習中，可引導學生參與真問題的項目學習，經歷建立數據模型、抽象模型、選擇數據結構、算法實現、上機調試、問題解決的全過程，從而促進學生形成和提高計算思維能力。

數據結構對算法效率的影響

一個算法的復雜度通常是由其輸入量決定的，隨著輸入的增加，不同算法的復雜度增長速度加快，如圖5所示。因此，為了降低算法復雜度，在設計算法時，應當同時考慮到輸入量的多少。

例如，教材中的顯示10000種商品中某個商品的價格問題，從數據結構上說，采用數組比鏈表更方便;但是如果在10000種商品中添加和刪除某一件商品，數據結構采用鏈表則要優于數組，這也說明了數據結構的不同選擇會影響算法的運行效率。

教師在教學過程中，還可以通過下面的程序，幫助學生更好地理解數據結構與算法效率的關系，具體程序代碼掃描文末二維碼。

當要進行商品信息的添加或刪除時，數據結構采用鏈表優于數組，因為在數組中插入或刪除某一個單元會引起大量其他數據的移動，時間復雜度為O（n），在鏈表中則只需對數據的“域”進行修改，時間復雜度為O（1）。

以上例題（程序）的實踐操作，有利于學生對數據結構專業知識的理解。學生在對時間復雜度、空間復雜度的程序驗證體驗過程中，能夠初步形成評估算法效率的能力和針對具體問題優化算法、數據結構的能力，有助于學科核心素養的養成和提高。