浦丕志 趙春芝

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

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

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

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

兩個(gè)程序的運(yùn)行結(jié)果相同，但從程序運(yùn)行時(shí)間來(lái)看，遞推算法優(yōu)于遞歸算法。

算法效率

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

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

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

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

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

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

從“常量階”和“線性階”的對(duì)比來(lái)看，算法對(duì)問(wèn)題解決的影響很大，也驗(yàn)證了研究算法復(fù)雜度的價(jià)值和意義。

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

時(shí)間復(fù)雜度

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

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

空間復(fù)雜度

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

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

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，記作S（n）。

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

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

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

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

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

4.以空間換時(shí)間

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

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

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

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

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

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

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

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

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