用Python驗證數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系

浦丕志 趙春芝

在計算機(jī)領(lǐng)域，算法實質(zhì)上就是針對所處理問題的需要，在數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上施加的一種運算規(guī)則。對問題中的數(shù)據(jù)的不同組織方式、解決問題的不同的策略將導(dǎo)致不同的算法。在解決實際問題時，要先分析其邏輯關(guān)系，建立抽象模型，再選擇合理的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)，通過算法解決其核心問題，實現(xiàn)解決問題的過程。

學(xué)生在學(xué)習(xí)實踐中，基本能夠合理選擇數(shù)據(jù)結(jié)構(gòu)和算法，但對算法的效率關(guān)注不多。在教學(xué)中，筆者以“求斐波那契數(shù)列的第19項的值”一題為例，讓學(xué)生體驗不同算法之間效率的差異性。

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

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

兩個程序的運行結(jié)果相同，但從程序運行時間來看，遞推算法優(yōu)于遞歸算法。

算法效率

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

在學(xué)生理解“問題規(guī)?！焙汀皶r間復(fù)雜度表述”方法后，筆者結(jié)合例題“求1+2+…+n的和”，幫助學(xué)生學(xué)習(xí)使用Python程序來驗證數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系。

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

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

方法2：用循環(huán)結(jié)構(gòu)實現(xiàn)1+2+…+n的求和（如下頁圖4）。

程序里面用到了循環(huán)結(jié)構(gòu)，當(dāng)問題規(guī)模n增大時，循環(huán)次數(shù)和“s=s+i”的累和過程也線性增大，時間復(fù)雜度為O（n）。

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

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

時間復(fù)雜度

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

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

空間復(fù)雜度

教材中通過問題與討論引導(dǎo)學(xué)生通過查閱相關(guān)資料，舉例說明空間復(fù)雜度如何度量。在教學(xué)時，建議教師鼓勵學(xué)生開展合作學(xué)習(xí)，通過資料查閱和討論，匯總學(xué)習(xí)經(jīng)驗，實現(xiàn)對“空間復(fù)雜度”的學(xué)習(xí)。指導(dǎo)學(xué)生進(jìn)行學(xué)習(xí)的步驟可以安排如下。

1.空間復(fù)雜度的概念

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

2.空間復(fù)雜度量度

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

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

3.數(shù)據(jù)結(jié)構(gòu)所占的空間復(fù)雜度

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

4.以空間換時間

現(xiàn)在的計算機(jī)存儲空間都非常大，通常都可以滿足程序?qū)Υ髷?shù)據(jù)存儲的需求，因此，在設(shè)計算法時，考慮更多的是優(yōu)化算法的時間復(fù)雜度，這就是“空間換時間”。

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

算法與數(shù)據(jù)結(jié)構(gòu)是問題求解中相輔相成、不可分割的兩個方面。在學(xué)習(xí)中，可引導(dǎo)學(xué)生參與真問題的項目學(xué)習(xí)，經(jīng)歷建立數(shù)據(jù)模型、抽象模型、選擇數(shù)據(jù)結(jié)構(gòu)、算法實現(xiàn)、上機(jī)調(diào)試、問題解決的全過程，從而促進(jìn)學(xué)生形成和提高計算思維能力。

數(shù)據(jù)結(jié)構(gòu)對算法效率的影響

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

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

教師在教學(xué)過程中，還可以通過下面的程序，幫助學(xué)生更好地理解數(shù)據(jù)結(jié)構(gòu)與算法效率的關(guān)系，具體程序代碼掃描文末二維碼。

當(dāng)要進(jìn)行商品信息的添加或刪除時，數(shù)據(jù)結(jié)構(gòu)采用鏈表優(yōu)于數(shù)組，因為在數(shù)組中插入或刪除某一個單元會引起大量其他數(shù)據(jù)的移動，時間復(fù)雜度為O（n），在鏈表中則只需對數(shù)據(jù)的“域”進(jìn)行修改，時間復(fù)雜度為O（1）。

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